  Heterogeneous information networks (HINs) represent different types of
entities and relationships between them. Exploring, analysing, and extracting
knowledge from such networks relies on metapath queries that identify pairs of
entities connected by relationships of diverse semantics. While the real-time
evaluation of metapath query workloads on large, web-scale HINs is highly
demanding in computational cost, current approaches do not exploit
interrelationships among the queries. In this paper, we present ATRAPOS, a new
approach for the real-time evaluation of metapath query workloads that
leverages a combination of efficient sparse matrix multiplication and
intermediate result caching. ATRAPOS selects intermediate results to cache and
reuse by detecting frequent sub-metapaths among workload queries in real time,
using a tailor-made data structure, the Overlap Tree, and an associated caching
policy. Our experimental study on real data shows that ATRAPOS accelerates
exploratory data analysis and mining on HINs, outperforming off-the-shelf
caching approaches and state-of-the-art research prototypes in all examined
scenarios.
  -- Note that this version of our work is more extended than the one presented
in TheWebConf 2023 (doi: 10.1145/3543507.3583322)
