# Atrapos: Evaluating Metapath Query Workloads in Real Time

Serafeim Chatzopoulos  0000-0003-1714-5225 Univ. of the Peloponnese &
IMSI, “Athena” RCGreece<EMAIL_ADDRESS>,  Thanasis Vergoulis  IMSI, “Athena”
RCGreece<EMAIL_ADDRESS>,  Dimitrios Skoutas  IMSI, “Athena” RCGreece
<EMAIL_ADDRESS>,  Theodore Dalamagas  IMSI, “Athena” RCGreece
<EMAIL_ADDRESS>,  Christos Tryfonopoulos  Univ. of the PeloponneseGreece
<EMAIL_ADDRESS>and  Panagiotis Karras  Aarhus UniversityDenmark
<EMAIL_ADDRESS>
###### Abstract.

_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.

##  1\. Introduction

_Heterogeneous information networks (HINs)_ , also known as _labeled property
graphs_ , offer an intuitive and generic model to encapsulate complex semantic
information via different types of nodes and edges (Shi et al., 2016b). By
this model, each node (or edge) has internal structure, including a set of
_properties_. By virture of the compactness of this model compared to those of
other types of _Knowledge Graphs_ like _RDF triple stores_ (Neumann and
Weikum, 2010; Weiss et al., 2008), HINs are increasingly supported by data
systems, e.g., Neo4j111https://neo4j.com/ (Asay, [n.d.]), and investigated in
research studies (Fang et al., 2021; Shen et al., 2014; Fang et al., 2020;
Jian et al., 2020; Sun et al., 2012a, b, 2011; Chen et al., 2021; Li et al.,
2021; Xie et al., 2021; Wang et al., 2020; Yang et al., 2020).

An example HIN capturing scholarly data, along with its implied _schema_ 222It
is worth mentioning that HINs are naturally schemaless, i.e., there is not any
technical requirement for a schema to be predetermined. However, the current
‘schema’ can be implied from the data and it can be conceptually useful in
some cases (e.g., this is why Neo4j gives this option with the call
db.schema() command. that represents the involved entity types, relationship
types, and properties, is illustrated in Figure 1. It consists of nodes
representing papers (P), authors (A), venues (V), and topics (T) and
(bidirectional) edges of three types: authors – papers (AP / PA), papers –
topics (PT / TP), and papers – venues (PV / VP).

Indirect relationships between entities are implicitly encoded by paths in the
HIN. In particular, all paths that correspond to the same sequence of node and
edge types (i.e., the same _‘metapath’_ (Sun et al., 2011)) encode latent
relationships of the same interpretation between the starting and ending
nodes. For example, in the HIN of Figure 1, the metapath $\langle
APTPA\rangle$ relates authors that have published papers on the same topic
(e.g., both ‘J. Doe’ and ‘H. Jekyll’ have papers about ‘DL’). It is also worth
mentioning that each metapath corresponds to a path on the schema of the HIN.

Metapaths are instrumental for HIN exploration and analysis from multiple
perspectives, as a means to derive different views of such a network. For
example, the metapath-based connectivity can be used to define node similarity
measures (Sun et al., 2011; Shi et al., 2014a, 2012; Y. Xiong, 2014) or to
rank nodes based on their centrality in a metapath-defined network (Shi et
al., 2016a; Ng et al., 2011; Li et al., 2014; Lee et al., 2012). In the
previous example, using the TPT metapath to perform a similarity join could
reveal that topics ‘ML’ and ‘DL’ are very related since they are involved in
two common papers. Moreover, to further elaborate the analysis, it is often
useful to apply property-based _constraints_ to a given metapath (e.g., in the
previous example, to consider only metapath instances involving papers
published later than ‘2020’). Motivated by the above, we have recently
developed prototypes for supporting metapath-based exploration and mining of
HINs (Chatzopoulos et al., 2020, 2021).

The first step in any metapath-based analysis is to generate a transformed
network that contains edges between all pairs of nodes connected with one or
more paths of the specified type. This preprocessing step is computationally
expensive. While various methods aim to speed up the computation of a _single_
metapath query, which typically involves a series of matrix multiplications
(Shi et al., 2016a), the problem becomes even more severe in scenarios calling
for the real-time evaluation of multiple metapath queries. In metapath-based
feature selection (Shi and Weninger, 2014; Meng et al., 2015), different
metapaths reveal different associations among entities, informing tasks like
recommendation and link prediction (Cao et al., 2014; Chen et al., 2018; Shi
et al., 2019). Such a task requires a large number of metapath queries (i.e.,
a _query workload_), leading to a significant bottleneck in the data analysis
process. Yet, in such a multi-query evaluation scenario, significant overlaps
typically occur among metapath queries (Finkelstein, 1982; Sellis, 1988;
Sellis and Ghosh, 1990; Roy et al., 2000; Kathuria and Sudarshan, 2017); such
overlaps are translated into repetitive matrix multiplications. We may thus
avoid a large portion of the heavy computations involved using query
materialization; yet, to the best of our knowledge, no existing approach does
so.

In this paper, we introduce Atrapos,333From Greek ἀτραπ´ος, ‘path’, what is
frequently trodden. a metapath query evaluation approach that detects, in real
time, frequent metapath overlaps within a sequence of queries. To do so, it
uses: (i) sparse matrix representations, which leverage the fact that the
matrices involved in metapath computations are largely sparse, especially for
constrained metapaths; and (ii) a tailored data structure with a customised
caching policy to materialise reoccurring intermediate results. Our
experimental evaluation demonstrates that Atrapos outperforms traditional,
single-query approaches in the evaluation of metapath query workloads, while
it is considerably faster than baseline approaches that we implemented. To the
best of our knowledge, this work is the first to study the problem of
optimizing the real-time evaluation of metapath query workloads. Our
contributions can be summarised as follows:

  * •

We show how metapath computations can be accelerated using matrix
multiplication algorithms tailored for sparse matrices along with an
appropriate cost model, especially when dealing with constrained metapaths.

  * •

We introduce a new data structure, the _Overlap Tree_ , that reveals overlaps
among metapaths and a cache insertion policy using this structure to cache and
reuse intermediate results in real-time while running a metapath query
workload.

  * •

We propose a tailored, effective cache replacement policy that exploits cache
item interdependence.

  * •

We conduct a thorough evaluation on real data showcasing the efficiency of our
approach.

The rest of the paper is structured as follows. In Section 2, we formally
define the problem. Section 3 introduces our approach, Atrapos. In Section 4,
we discuss our experimental evaluation. Section 5 reviews related work and
Section 6 concludes the paper.

Figure 1. An example HIN and its implied schema.

##  2\. Problem Definition

Here, we introduce the basic concepts and notations we use, and define the
problem of _metapath query workload evaluation_ (MQWE).

A _heterogeneous information network (HIN)_ (Shi et al., 2016b; Sun et al.,
2011), also known as knowledge graph, is a directed multigraph that contains
multiple types (or _labels_) of nodes and edges:

###### Definition 0 (HIN).

A _HIN_ is a tuple $\mathcal{H}=\langle V,E,O,R,\phi,\psi\rangle$, where $V$
and $E$ are the nodes and edges of a directed multigraph, respectively; $O$
and $R$ $(|O|>1$, $|R|>1)$ are the sets of distinct node and edge types,
respectively, while $\phi:V\rightarrow O$ and $\psi:E\rightarrow R$ are the
mapping functions that determine the type of each node $v\in V$ and each edge
$e\in E$, respectively.

It is often useful to consider that each node type comes with a set of
_properties_ , which capture useful information for the nodes of that
type.444It may be useful to assign properties to edges, as well, however for
notation simplicity in this work we do not consider edge properties. Given a
node $v\in V$, we use the notation $v.prop$ to refer to the value of the
property $prop$ on $v$. All distinct node and edge types, along with the
respective properties, can be easily derived by the HIN data and we often
refer to them as the HIN’s _schema_. Finally, it is often convenient (for
various types of analysis) to represent the edges of a particular type $r=$
ȯö, where ȯ,ö $\in O$ and $r\in R$, using the respective _adjacency matrix_
$A_{r}$, i.e., a ȯ $\times$ ö matrix for which $A_{r}[i,j]=1$ if the $i^{th}$
node of type ȯ is connected with the $j^{th}$ node of type ö, and
$A_{r}[i,j]=0$ otherwise.

A _metapath_ is a sequence of node types connected by appropriate edge types,
hence corresponds to a path on a HIN schema. Given a metapath $m$, every path
in the HIN that complies to the sequence of node and edge types specified by
$m$ is an _instance_ of $m$. Formally:

###### Definition 0 (Metapath & Metapath instance).

Given a HIN $\mathcal{H}=\langle V,E,O,R,\phi,\psi\rangle$, a _metapath_ $m$
on $\mathcal{H}$ is a sequence $m=\langle
o_{1}\xrightarrow{r_{1}}o_{2}\dots\xrightarrow{r_{n-1}}o_{n}\rangle$, where
$o_{i}\in O$, $r_{j}\in R~{}\forall i,j$, and $n$ is the metapath _length_. An
_instance_ of $m$ is any path $\langle
v_{1}\xrightarrow{e_{1}}v_{2}\dots\xrightarrow{e_{n-1}}v_{n}\rangle$ for which
$v_{i}\in V$, $e_{j}\in E$, $\phi(v_{i})=o_{i}$, and $\psi(e_{j})=r_{j}$
$\forall i,j$.

By a common simplification (Shi et al., 2016a; Sun et al., 2011), we denote a
metapath as $m=\langle o_{1}o_{2}\dots o_{n}\rangle$, without edge types, when
there is only a single edge type between any pair of node types. It should be
highlighted that this convention is followed here solely for the sake of
simplicity; all approaches can easily accommodate edges of different types
among the same pairs of nodes (e.g., since they employ separate adjacency
matrices for distinct edge types). Figure 1 shows an example HIN comprising
$14$ nodes of $4$ types ($A$, $P$, $V$ and $T$) and $3$ edge types ($AP/PA$,
$PV/VP$, and $PT/TP$). A simplified metapath of length $3$ is $m=\langle
APV\rangle$, and an instance of $m$ is the path $\langle$‘$Y.Vuvuli$’ ‘$P3$’
‘$VLDB$’$\rangle$.

We also consider metapaths enhanced with constraints on node type properties,
which restrict the nodes that may participate in a metapath instance. We refer
to such metapaths as _constrained metapaths_. The set of instances of a
constrained metapath is a subset of those of the corresponding unconstrained
metapath. Formally:

###### Definition 0 (Constrained metapath).

A _constrained metapath_ is a pair $m^{\prime}=(m,C)$ where $m=\langle
o_{1}o_{2}\dots o_{n}\rangle$ is a metapath and $C=\\{c_{1},\dots,c_{n}\\}$ is
a set of constraints on the nodes in $m$.

Figure 2. Evaluation of the $m=(\langle APT\rangle,\\{P.year>2020\\})$ query
on the HIN of Figure 1.

Recall the metapath $\langle APTPA\rangle$ of the HIN in Figure 1, which
connects two authors that have published a paper on the same topic. A data
scientist working with this HIN may need to examine only recent papers, e.g.,
papers published after $2000$, may use the constrained metapath
$m^{\prime}=(\langle APTPA\rangle,\\{P.year>2000\\})$.

We now define the _metapath query evaluation_ (MQE) problem.

###### Problem 1 (MQE).

Given a HIN $\mathcal{H}=\langle V,E,O,R,\phi,\psi\rangle$ and a (constrained)
metapath $m=(\langle o_{1}o_{2}\ldots o_{n}\rangle,C)$, MQE retrieves all node
pairs $\langle v_{o},v_{d}\rangle$, such that $v_{o}\in o_{1}$, $v_{d}\in
o_{n}$, and $v_{o}$ is connected to $v_{d}$ based on at least one instance of
$m$. We refer to each such pair, along with the respective number of
instances, as an _MQE result_ for $m$.

A conventional approach to evaluate a metapath query $m$ is to calculate the
matrix product $A_{m}=A_{o_{1}o_{2}}A_{o_{2}o_{3}}...A_{o_{n-1}o_{n}}$, where
$A_{o_{i}o_{j}}$ is the adjacency matrix for the relation $r=o_{i}o_{j}$. Each
non-zero element in $A_{m}$ is a response to the corresponding metapath query.
Given a constraint $c_{i}\in C$ on object $o_{i}$ in relation $r=o_{i}o_{j}$,
we apply $c_{i}$ in the matrix product via the _constrained_ adjacency matrix
$A^{c_{i}}_{o_{i}o_{j}}=M_{c_{i}}\cdot A_{o_{i},o_{j}}$, where $M_{c_{i}}$ is
a $|o_{i}|\times\ |o_{i}|$ diagonal matrix that has element $1$ in the
diagonal only for nodes $o_{i}$ satisfying $c_{i}$. Figure 2 shows an example
for the metapath query $m=(\langle APT\rangle,\\{P.year>2020\\})$. Based on
the MQE problem, we define the _metapath query workload evaluation (MQWE)_
problem:

###### Problem 2 (MQWE).

Given a HIN $\mathcal{H}=\langle V,E,O,R,\phi,\psi\rangle$ and a metapath
query workload $W=\\{m_{1},\dots,m_{q}\\}$, MQWE is the task of efficiently
computing all $MQE$s for the metapaths in $W$.

We focus on MQWE and elaborate our approach in the following.

##  3\. The Atrapos approach

Atrapos, our approach for efficiently evaluating metapath query workloads, (a)
translates metapath query evaluation into a sequence of multiplications
between the adjacency matrices of the edge types contributing to the
respective metapaths, and (b) applies dynamic programming to identify an
efficient order of multiplications (Section 3.1). Going beyond the state of
the art (Shi et al., 2016a), Atrapos takes into account the inherent sparsity
of the adjacency matrices to exploit fast sparse matrix multiplication
algorithms, and identifies improved execution plans for each metapath using
matrix multiplication cost models tailored for sparse matrices (Section 3.2).
Lastly, Atrapos identifies sub-metapaths that reoccur due to metapath overlaps
in a workload and caches the corresponding matrix multiplication results to
avoid repeating them. To do so, it uses a specialized data structure, the
_Overlap Tree_ , which keeps track of metapath overlaps, occurrence
frequencies, and cache entries (Section 3.3); Atrapos’s cache management
policy exploits the Overlap Tree to avoid undesirable cache replacements
(Section 3.4).

###  3.1. Efficient Multiplication Plan Selection

Given a metapath query, Atrapos generates a set of alternative execution
plans, each comprising a different sequence of multiplications between the
adjacency matrices of the edge types involved, as in (Shi et al., 2016a). Due
to associativity, there are many such orderings that produce the same result,
and their computational costs may differ. For example, consider the query
$m=\\{\langle APT\rangle,P.year>2020\\}$ in Figure 2. The result
$A_{m}=A_{AP}\cdot M_{P.year>2020}\cdot A_{PT}$ can be calculated as
$(A_{AP}\cdot M_{P.year>2020})\cdot A_{PT}$ or
$A_{AP}\cdot(M_{P.year>2020}\cdot A_{PT})$. Since $A_{AP}$, $M_{P.year>2020}$,
and $A_{PT}$ are of size $[4\times 5]$, $[5\times 5]$, and $[5\times 3]$,
respectively, and a standard multiplication of two matrices of size $m\times
n$ and $n\times l$ requires $m\cdot n\cdot l$ operations, the first option
yields $160$ operations, while the second $135$, which is preferable.

By this standard implementation of matrix multiplication, the cost
$C_{A_{i...j}}$ of the optimal plan for a multiplication series
$A_{i...j}=A_{i}\cdot...\cdot A_{j}$, $1\leq i<j$ via dynamic programming (DP)
(Cormen et al., 2009), is:

(1) $C_{A_{i...j}}=\min\limits_{i\leq
k<j}\\{C_{A_{i...k}}+C_{A_{k+1...j}}+c_{A_{i...k}\cdot A_{k+1...j}}\\}$

where $C$ is a $p\times p$ matrix of optimal costs and $c_{A_{i...k}\cdot
A_{k+1...j}}$ the cost of multiplying the results of sub-series $A_{i...k}$
and $A_{k+1...j}$, estimated by matrix dimensions in the case of standard
matrix multiplication.

###  3.2. Sparse Matrix Representation

The technique of Section 3.1 has been used to identify the optimal matrix
multiplication plan for single metapath query evaluation (Shi et al., 2016a).
However, most adjacency matrices in HINs are sparse (i.e., have few non-zero
elements). Using a general-purpose matrix multiplication method on sparse
matrices is inefficient. This sparsity is amplified if there are constraints
in the metapath queries, which are represented by extra diagonal matrices with
a small number of non-zero elements in the diagonal, whose multiplication with
other matrices yields an even sparser result. Unfortunately, previous work
opted for dense matrix representations (Shi et al., 2016a).

By contrast, we use sparse matrix structures to represent adjacency matrices
and multiply such matrices taking advantage of these structures. Still, the
cost to multiply sparse matrices cannot be adequately estimated from their
dimensions, as it also depends on the number of non-zero elements in input and
result matrices, implementation details, and memory accesses. An approximation
model (Kernert et al., 2015) estimates the cost of multiplying sparse matrices
$X~{}[m\times n]$ and $Y~{}[n\times l]$ to yield $Z=X\cdot Y$ as:

(2) $\hat{c_{X\cdot Y}}\approx\alpha\cdot\underbrace{(m\cdot
n\cdot\rho_{X})}_{\text{$nonZero(X)$}}+\beta\cdot\underbrace{(m\cdot
n\cdot\rho_{X}\cdot
l\cdot\rho_{Y})}_{\text{$\hat{N_{op}}$}}+\gamma\cdot\underbrace{(m\cdot
l\cdot\hat{\rho_{Z}})}_{\text{$\hat{nonZero(Z)}$}}$

where $\rho_{X}$ and $\rho_{Y}$ are the densities of $X$ and $Y$, $nonZero(X)$
the number of non-zero elements in $X$, $\hat{N_{op}}$ the estimated number of
operations, $\hat{\rho_{Z}}$ the estimated density of $Z$, and
$\hat{nonZero(Z)}$ the estimated number of non-zero elements in $Z$.
Coefficients $\alpha,\beta,\gamma$ are determined by multilinear regression
using least squares fit.

Assuming that the non-zero elements in $X$ and $Y$ are uniformly distributed,
we compute $\hat{\rho_{Z}}=1-(1-\rho_{X}\cdot\rho_{Y})^{n}$ as indicated by
the average-case density estimator $E_{ac}$ (Kernert et al., 2015; Sommer et
al., 2019). There exist more accurate estimation algorithms (Kernert et al.,
2015; Sommer et al., 2019; Cohen, 1998; Yu et al., 2017), taking into
consideration the pattern of non-zero elements in $X$ and $Y$, yet they incur
a higher computational cost. We found experimentally that cost estimation
techniques do not provide significant benefits in our application scenario.
Figure 3 illustrates the execution time breakdown of $E_{ac}$ against the MNC
estimator (Sommer et al., 2019), which builds sketches to estimate the
sparsity of the result. This experiment considers $2\,000$ randomly selected
metapath queries with their length varying from $3$ to $5$ for the Scholarly
and News article HINs (see Sections 4.1.1 and 4.1.2). Both estimators achieve
very comparable results for the actual matrix multiplication execution, with
$E_{ac}$ requiring a negligible amount of time for planning compared to MNC.
Interestingly, both estimators produce the same multiplication plans for over
$70\%$ of the examined queries. As we consider constrained metapath queries,
very sparse matrices arise in the multiplication, and the plans produced by
$E_{ac}$ are on par with those of more sophisticated solutions without the
added cost of planning. Since the added cost of more accurate estimators does
not pay off in terms of cost savings for the query types we examine, we
settled for the former best-effort estimation.

Figure 3. MNC vs the average-case density estimator $E_{ac}$ (log scale on
y-axis).

In a nutshell, our sparsity-aware method produces a multiplication plan for a
metapath query by the dynamic programming approach of Equation 1, while
estimating sparse-matrix multiplication costs by Equation 2. We use an
additional $p\times p$ matrix $D$ to hold the densities $\hat{\rho_{Z}}$ of
intermediate results needed to compute this cost in each step. Besides, since
Atrapos caches intermediate matrix multiplication results (Section 3.4), we
substitute these estimates with the (negligible) cost of retrieving a result
matrix from the cache, or the cost of recomputing a result matrix if that had
been previously cached and then evicted from the cache (Section 3.3).

###  3.3. The Overlap Tree

The hitherto discussed techniques focus on a single metapath query. We further
enhance the evaluation of a metapath query workload by avoiding redundant
computations that arise due to query overlaps. To do so, we introduce the
_Overlap Tree_ , a dynamic data structure that organizes information about
frequent metapath overlaps in the workload and their dependencies. We use this
data structure, along with a cache memory that stores matrix multiplication
results for the indexed overlaps, to further reduce the workload evaluation
time. We provide details on cache management in Section 3.4.

####  3.3.1. The structure

The Overlap Tree is a dynamic data structure that keeps track of overlaps and
dependencies between the already evaluated and new queries during the
evaluation of a metapath query workload. It is progressively constructed by
parsing query metapaths, accompanied by a cache memory that stores matrix
multiplication results. At any time, it encodes the overlaps of hitherto
evaluated queries, their constraints, their occurrence frequencies, and
pointers to any corresponding cache entries. We first describe the structure
of the Overlap Tree ignoring query constraints; we explain how the tree
considers constraints in Section 3.3.4.

Each internal node of the tree represents an observed metapath overlap and
contains the following information:

  * •

_Frequency ( $f$)_: The number of occurrences of the respective overlap in the
query workload until the given time point.

  * •

_Cache entry pointer ( $p$)_: A pointer to the cache entry containing the
result of the multiplication represented by the overlap. If this result is not
in the cache (i.e., has never been cached or has been cached and evicted), the
pointer is null.

  * •

_Multiplication cost ( $c$)_: The time required to perform the matrix
multiplication that corresponds to the overlap.

  * •

_Matrix sparsity ( $\rho$)_: The number of non-zero elements in the
multiplication result matrix for that overlap.

In addition, the Overlap Tree contains one leaf node for each suffix of the
metapaths of already evaluated queries (considering the metapath as a
string555A query-specific character is added at the end of each metapath
string to guarantee the correspondence of leaves to query suffixes in case of
common prefixes. For simplicity, in all the examples we ignore this special
character.); the internal structure of each leaf is identical to that of
internal nodes.666Note that $f=1$ always for leaves. Each edge of the tree is
labelled with a non-empty string, such that the concatenation of edge labels
on a tree traversal from the root to a node gives the string that encodes the
respective metapath overlap (or suffix in the case of leaves).

The Overlap Tree is inspired from the _generalised suffix tree_ (Szpankowski,
1993; Bieganski et al., 1994), which captures the substrings of a given
collection of strings; it adds pointers to cached items and information on
overlap frequency, query constraints, and matrix multiplication costs. We
emphasize that, as its name suggests, the Overlap tree produces a cache entry,
and, for that matter, a node, only if an overlap is detected.

Figure 4. Example workload and Overlap Tree.

Figure 4 depicts an Overlap Tree for a workload of three metapath queries
($q_{0}$, $q_{1}$, and $q_{2})$, defined on the _News Articles_ HIN (used in
Section 4). The highlighted node represents the overlap sub-metapath $ICPA$,
occurring in all three queries, points to a cache entry for the multiplication
result $A_{IC}\cdot(A_{CP}\cdot A_{PA})$, and stores the sparsity $s$ of this
cached result and the cost $c$ to calculate it.

####  3.3.2. Update

We construct an Overlap Tree from a metapath query workload
$W=\\{m_{1},m_{2},...,m_{q}\\}$ by sequentially inserting into the tree all
metapath queries $m_{i}\in W$. For each $m_{i}$ of length $l_{i}=|m_{i}|$,
we777This process is described due to its simplicity and it is not the most
efficient approach to build an Overlap Tree. Approaches based on Ukkonen’s
algorithm (Ukkonen, 1995) are significantly faster, yet their description is
beyond the scope of this work. insert the entire $m_{i}$ and all its suffixes
$s_{i}=m_{i}[k:l_{i}]$ with $0<k<l_{i}$. Starting from the root, we find the
longest path that matches a prefix of $s_{i}$; the match ends either at an
existing node or in the middle of an edge. In both cases, we let an internal
node represent the detected overlap after the last matching character at
position $c$, corresponding to sub-metapath $m_{i}[k:c]$; if the match ends on
a leaf node, that node becomes internal, assigned dummy leaves if necessary.
In case that occurs on an edge, we break that edge in two edges labelled with
$m_{i}[k:c]$ and $m_{i}[c+1:l_{i}]$, and create a new internal node. Lastly,
we create a new leaf node that corresponds to $s_{i}$ and is connected to the
last traversed internal node with a new edge. In this procedure, node
frequencies are updated so as to reflect sub-metapath occurrences.

After this traversal, the cache pointers of the involved nodes may be updated.
In particular, for the node representing the whole query $m_{i}$, the update
algorithm will attempt to cache the respective multiplication result, if the
node’s cache item pointer is currently null; cache insertion depends on the
_cache replacement policy_ (Section 3.4.2). Similarly, a cache insertion will
be attempted for any traversed internal node in case the respective
intermediate matrix multiplication result is calculated according to the
selected multiplication plan (see Sections 3.1 & 3.2). Yet even if the
corresponding intermediate result is produced, it is not guaranteed to be
cached, as that depends on the _cache insertion policy_ (Section 3.4.1).

####  3.3.3. Space Complexity

Consider a metapath query workload $W=\\{m_{1},m_{2},...,m_{q}\\}$ and the
respective Overlap Tree $T_{W}$. The exact number of leaves in $T_{W}$ is
$\lambda=|m_{1}|+|m_{2}|+...+|m_{q}|$, since each $m_{i}\in W$ has exactly
$|m_{i}|$ suffixes. As an internal tree node is created when and only when
detecting an overlap among queries, each internal node has at least two
children; in the worst case, all internal nodes have exactly two children,
hence the Overlap Tree is a full binary tree having $2\lambda-1=O(\lambda)$
nodes.

Based on the internal structure of the Overlap Tree nodes, all leaves have the
same memory footprint: the aggregated size of integer $f$, two floating point
numbers, $c$ and $\rho$, and one pointer $p$. All internal nodes, on the other
hand, have the same memory footprint plus the size of the pointers to their
children. Since in the worst case each internal node has two such pointers,
the respective worst-case size can be easily calculated. Finally, the root has
a memory footprint equal to that of two pointers, since none of the four node
variables ($f,c,\rho,p$) are included in this node.

It is worth to highlight that for most practical scenarios, like those
examined in our experiments, the size of the Overlap Tree is negligible
compared to the size of the available main memory of a contemporary server.
This means that the structure allows for a large size of cache to be
determined, benefiting the performance of the workload evaluation process.

####  3.3.4. Handling constrained queries

We have described Overlap Tree operations without considering query
constraints (see Definition 2.3 for details on constrained metapaths). To
support constraints, we modify the internal structure of the tree nodes
enriching them with a key-value data structure, called the _constraints index_
, that holds a given constraint in the form of a string (e.g., $P.year>2000$)
as key and the respective variables ($f$, $p$, $c$, and $\rho$) as a composite
value. The constraint index of each node can be implemented as a suitable data
structure, such as a hash table index. We adapt the respective operations
accordingly to accommodate this change.

Specifically, upon probing the Overlap Tree for a constrained pattern, we
traverse the tree starting from the root following the exact same process
described in Section 3.3.2 until we reach the ending node. Then, we probe the
constraints index of the node to retrieve the respective entry (or to create
it, if there is not one) and we update the corresponding constraints index
counters accordingly; if we select to cache the result, the cache entry
pointer should also be updated.

Regarding space complexity, the calculations in Section 3.3.3 remain valid,
yet we should also take into consideration the number of constraints each node
accommodates in the constraint index. Since each leaf node represents a
single, non-overlapping metapath suffix (i.e., $f=1$), each leaf stores only
one key-value pair. By contrast, each internal node represents a metapath
query overlap (i.e., $f>1$); in the worst case, each overlapping metapath
query has a different constraint, hence the number of key-value pairs in a
node equals the node’s frequency $f$.

###  3.4. Atrapos-OTree Cache Management

Figure 5. Overlap Tree with cache entry dependencies.

Evaluating a metapath query workload can benefit from caching and reusing any
reappearing intermediate matrix multiplication results. However, such results
are unlikely to all fit in a typical machine’s main memory. We thus need a
cache management policy.

We exploit the Overlap Tree to obtain a two-fold benefit: first, we use the
Overlap Tree to inform a _cache insertion policy favoring the insertion of
frequent multiplication results_ ; thereby we avoid caching matrix
multiplications that appear rarely, hence reduce unnecessary cache evictions
(Section 3.4.1); secondly, we use the Overlap Tree to obtain information on
cached items (such as computational cost to produce, size, and dependencies)
for a tailored _cache replacement policy_ (Section 3.4.2). In the following,
we elaborate on these two uses of the Overlap Tree by Atrapos’s cache
management policy, the Atrapos-OTree policy.

####  3.4.1. Atrapos-OTree Cache Insertion Policy

In any domain of knowledge, certain informative sub-metapaths are bound to
occur frequently in a query workload. Such metapath repetitions may lead to
redundant matrix multiplications during the evaluation of a workload.
Materializing intermediate multiplication results in cache can reduce the
number of redundant computations, hence improve performance. However, as there
are numerous intermediate results, we need a cache insertion policy to select
which ones to insert.

The Overlap Tree is helpful to that end, as each _internal_ node thereof
encodes a sub-metapath occurring at least twice in the workload (Section
3.3.2). Our cache insertion policy attempts to insert a cache entry for (i)
the whole of $m$ and (ii) the longest part of $m$ that matches an internal
tree node (i.e., has occurred at least twice) _and_ an intermediate result
calculated by the matrix multiplication plan. Our cache replacement policy
(Section 3.4.2) determines whether this attempt succeeds. Thereby, Atrapos
reduces cache insertion attempts, focusing on frequent overlaps, which are
likely to reoccur. Moreover, it selects to cache longest qualifying sub-
metapath, which usually has the largest computational cost. For instance, in
Figure 5 although $CPA$ and $ICPA$ are equally frequent and their intermediate
results are available, only the latter is cached.

1

2$L=0$

3 foreach  _request of cache item $p$_ do

4 $f_{p}=f_{p}+1$

5 if  _$p$ is in cache_ then

6 $p_{l}=L$

7 $h_{p}=f_{p}\cdot c_{p}/s_{p}+p_{l}$

8 else

9 while  _not enough space for $p$ in cache_ do

10 $L=min\\{h_{q}|q\in cache\\}$

11 evict $q$ that satisfies $h_{q}=L$

12 foreach  _cache entry $e$ in the subtree of $q$_ do

13 $c_{e}=c_{e}+c_{q}$

14 $h_{e}=f_{e}\cdot c_{e}/s_{e}+e_{l}$

15

16 insert $p$ in cache

17 $p_{l}=L$

18 $h_{p}=f_{p}\cdot c_{p}/s_{p}+p_{l}$

19 foreach  _cache entry $e$ in the subtree of $p$_ do

20 $c_{e}=c_{e}-c_{p}$

21 $h_{e}=f_{e}\cdot c_{e}/s_{e}+e_{l}$

22

23

Algorithm 1 Atrapos-OTree cache replacement policy

####  3.4.2. Atrapos-OTree Cache Replacement Policy

A straightforward way to cache matrix multiplication results is to use a
generic policy, like LRU (Aho et al., 1971), which discards the _least
recently used_ cached item first. LRU works well when all items have similar
(a) cost to fetch and (b) size. However, neither of these conditions holds for
metapath query workloads, as (i) fetching an item in the cache involves matrix
multiplications, whose cost differs among items, and (ii) item size varies
depending on the result matrix density. In effect, one may adopt a size- and
cost-aware cache replacement policy, as in web server caching (Bahn et al.,
2002; Jin and Bestavros, 2001; Shudong Jin and Bestavros, 2000). Popularity-
aware Greedy Dual-Size (PGDS) (Shudong Jin and Bestavros, 2000) measures the
utility of a cache entry $e$ as $u_{e}=f_{e}\cdot\frac{c_{e}}{s_{e}}$, where
$f_{e}$ is the frequency of $e$, $c_{e}$ its cost, and $s_{e}$ its size. We
may obtain $f_{e}$ of each cache entry from the corresponding tree counter,
$c_{e}$ as the estimated cost of the corresponding matrix multiplication, and
$s_{e}$ as its size. Let $E$ be all cache entries. Initially, each entry
$e_{i}\in E$ has utility value $h_{e_{i}}=u_{e_{i}}$. In case of cache
saturation, we evict the entry with $\min\\{h_{e_{i}}\\}$, denoted as
$H_{\min\\\ }$ and reduce the utility values of all other cache items by
$H_{\min\\\ }$. Thus, recently cached items retain a higher fraction of their
initial utility and are hence less likely to be evicted. To avoid subtracting
$H_{\min\\\ }$ from items in the cache, PGDS uses an inflation variable $L$:
it adds $H_{\min\\\ }$ to $L$ at each eviction, and increases the utility of
any cache hit by $L$.

We employ an enhanced cache policy that builds on PGDS by considering cache
entry interdependence: the cost $c_{e}$ to re-calculate and re-fetch an entry
$e$ in the cache may be smaller than what PGDS estimates, because part of the
calculation may be obtained by another cache entry, $e^{\prime}$, as cache
entries follow a hierarchy: given an internal Overlap Tree node $n_{p}$ and
the set of nodes in its sub-tree, $S(n_{p})$, the cache entry of each
$n_{i}\in S(n_{p})$ can exploit that of $n_{p}$. Thus, each time we insert a
cache entry $p$ in an internal node, we _subtract_ its cost $c_{p}$ from that
of cached items in its sub-tree, as these are cheaper to recompute given $p$.
In reverse, when we evict an entry $q$ from the cache, we _reinstate_ its cost
$c_{q}$ to that of items in its sub-tree. Algorithm 1 outlines this approach.

Figure 5 shows the Overlap Tree of Figure 4 after inserting a new metapath,
$ICPALA$. Assuming that the pointer $p$ in the highlighted node for $ICPAL$
was previously null, we insert a new cache item, containing the respective
multiplication result, and update $p$ to point to it. Still, since the
traversal passed through the node for $ICPA$, we can use its cached result to
calculate the result for $ICPAL$. In case the cached item for $ICPA$ is
evicted, we reinstate its cost to that of cached items in its sub-tree, i.e.,
to $ICPAL$, to reflect the cost of its calculation without using the entry for
$ICPA$.

##  4\. Experimental Evaluation

In this section, we present an extensive experimental evaluation of Atrapos.
We describe the experimental setup in Section 4.1, showcase the performance of
Atrapos against state-of-the-art approaches for single metapath query
evaluation in Section 4.2, and present experiments against two baselines that
take advantage of a caching mechanism for metapath workloads in Section 4.3;
we investigate various cache replacement policies in Section 4.4.

###  4.1. Setup

####  4.1.1. Datasets.

We use the following data sets:

  * •

Scholarly HIN. A dataset based on AMiner’s DBLP Citation Dataset (Tang et al.,
2008), enriched with projects funded by the EU under the Horizon 2020
programme, taken from
Cordis888https://data.europa.eu/euodp/en/data/dataset/cordisH2020projects,
including entities for Papers (P), Authors (A), Organisations (O), Venues (V),
Topics (T), and Research Projects (R). Figure 6(a) shows the implied schema.

  * •

News articles HIN. This is based on news articles published on April 2016 and
their associated entities from the GDELT Project (Leetaru and Schrodt, 2013),
enriched with information for people involved in the Panama Papers scandal and
their related companies and intermediaries from the Offshore Leaks
database999https://offshoreleaks.icij.org/pages/database). The integration was
performed by linking Panama Papers officers with persons in GDELT. The
resulting HIN comprises Articles (A), Organisations (O), Persons (P),
Locations (L), Sources (S), Themes (T), Companies (C), and their
Intermediaries (I). Its implied schema is shown in Figure 6b.

(a) Scholarly HIN

(b) News articles HIN

Figure 6. Implied schemas of experimental HINs. Table 1. Details of experimental HINs. Dataset | Contained Core | Nodes | Edges | Avg. Degree
---|---|---|---|---
| Entity Nodes | (in millions) | (in millions) |
| $60\%$ | $8.65$ | $108.43$ | $25.06$
Scholarly HIN | $80\%$ | $10.44$ | $148.09$ | $28.36$
| $100\%$ | $12.15$ | $190.99$ | $31.43$
| $60\%$ | $7.71$ | $173.38$ | $44.92$
News articles HIN | $80\%$ | $10.06$ | $233.33$ | $46.37$
| $100\%$ | $12.43$ | $298.11$ | $47.95$

To assess scalability, we consider two additional splits of different sizes
for the aforementioned HINs, containing $60\%$ and $80\%$ of their core
entities, i.e. papers and articles, while preserving nodes and edges connected
with them. On News articles HIN, we first keep across splits all articles
connected with companies, as otherwise few or no companies may be present in
the final dataset, and we then augment this core set to reach the number of
articles needed. Table 1 shows their statistics, i.e., number of nodes and
edges, while Table 2 collects the number of nodes and edges per type for each
dataset split. Note that, in all cases, we consider bi-directional
relationships between entities. These HINs are two orders of magnitude larger
than those considered in previous recent studies (e.g. (Shi et al., 2016a)).

Table 2. Number of nodes/edges per type. | Node | Million nodes per split | Edge | Million edges per split
---|---|---|---|---
| Type | $\mathbf{(60\%~{}/~{}80\%~{}/~{}100\%)}$ | Type | $\mathbf{(60\%~{}/~{}80\%~{}/~{}100\%)}$
Scholarly HIN | P | $2.936/3.915/4.894$ | PP | $16.367/29.236/455.641$
A | $3.100/3.781/4.398$ | AP/PA | $17.916/23.898/29.869$
O | $2.488/2.608/2.706$ | OA/AO | $14.921/15.976/16.832$
V | $0.009/0.009/0.010$ | VP/PV | $5.247/6.994/8.743$
T | $0.117/0.125/0.132$ | TP/PT | $53.977/71.974/89.974$
R | $0.001/0.001/0.001$ | RP/PR | $0.008/0.010/0.013$
News articles HIN | A | $4.394/5.859/7.324$ | IC/CI | $0.010/0.010/0.010$
O | $1.153/1.486/1.829$ | OA/AO | $25.786/35.186/45.584$
P | $1.953/2.465/2.995$ | PA/AP | $32.902/44.334/57.125$
| L | $0.172/0.202/0.229$ | LA/AL | $31.767/42.985/55.319$
| T | $0.014/0.016/0.17$ | TA/AT | $73.184/97.618/122.750$
| S | $0.022/0.025/0.030$ | SA/AS | $9.714/13.185/17.306$
| C | $0.005/0.005/0.005$ | CP/PC | $0.014/0.014/0.014$
| I | $0.001/0.001/0.001$ |  |

####  4.1.2. Query Workloads

Due to the lack of available real-world workloads, we create synthetic query
workloads simulating the query patterns of multiple data scientists posing
queries, each exploring different aspects of a certain entity (e.g., a
particular author in the Scholarly HIN) via consecutive metapath queries
related to it. The entity of interest is determined by an equality constraint.
We refer to such a set of constrained metapath queries as a _query session_.
We generate such queries by randomly choosing a metapath and a constraint
applied on it. In each step, we either (a) randomly pick a new constraint and
start a new session, with _session restart probability_ $p$, or (b) continue
using the same constraint and pick a different metapath, with probability
$1-p$. Indicatively, $p=0.1$ results in sessions each containing on average
$10$ metapath queries, which is a reasonable length. Eventually, we shuffle
all queries in a workload to simulate a real-world environment. For all random
selections we used a uniform or a zipfian probability distribution, the former
as default. Each query workload contains $500$ metapath queries with length
ranging from $3$ to $5$. We repeat each experiment with $10$ different query
workloads, and report the average evaluation time. All the query workloads are
openly available.101010https://github.com/atrapos-
hin/artifacts/tree/main/workloads

####  4.1.3. Methods

We juxtapose the following methods:

  * •

_HRank_ : the approach of (Shi et al., 2016a) in its original configuration.

  * •

_Neo4j_ (Webber, 2012): a well-established graph database. We convert each
metapath query to its corresponding Cypher111111Neo4j’s native query language:
https://neo4j.com/developer/cypher-query-language/ query, using the
parameters’ syntax121212https://neo4j.com/docs/cypher-
manual/current/syntax/parameters/ to express query constraints, enabling Neo4j
to cache query execution plans.

  * •

_HRank Sparse (HRank-S)_ : a version of HRank adjusted to exploit sparse
matrix representations and the cost estimation for sparse matrix
multiplications of Section 3.2.

  * •

_Cache-based Baseline-1 (CBS1)_ : an adaptation of HRank-S using an LRU cache
to store _final_ metapath query results.

  * •

_Cache-based Baseline-2 (CBS2)_ : an extension of _CBS1_ that caches all
_intermediate_ matrix multiplication results.

  * •

_A trapos_: our approach that uses the Overlap Tree to detect frequent query
overlaps and cache entry dependencies.

_HRank_ and _Neo4j_ are state-of-the-art approaches for single metapath query
evaluation which we apply on query workloads. _Neo4j_ has its own internal
caching mechanism. As discussed in Section 4.2, these approaches perform
poorly even for small datasets and do not scale to large HINs. Therefore, we
also use the three baselines (_HRank-S_ , _CBS1_ , and _CBS2_), which take
advantage of sparse matrix representations and simple caching mechanisms. Note
that, all intermediate results evicted from the cache could, in theory, be
stored on disk instead of discarding them, acting like a second level cache
mechanism. However, this applies to all cache-based methods and, hence, does
not impact their relative comparison.

####  4.1.4. Evaluation Setting

We implemented131313Code available at https://github.com/atrapos-hin/artifacts
all methods in C++, using the Eigen Linear Algebra Library (Guennebaud et al.,
2010) for matrix multiplications. We opted for one of the most popular sparse
matrix data structures, which stores non-zero values and their positions in a
column-major order, the compressed sparse column layout (CSC).141414CSC is the
recommended sparse matrix layout in Eigen:
https://eigen.tuxfamily.org/dox/group__TopicStorageOrders.html All source
codes were compiled with the GNU Compiler (G++ version 9.3.0) with o3
optimization enabled and the NDEBUG preprocessor directive that suppresses
assertions to reduce execution time. All cache-based implementations are set
to never store items that exceed a size threshold equal to $80\%$ of the
available cache size. This rule safeguards against evicting many useful
results to store just a single large one (indicatively, the rule applied in
less than $0.1\%$ of the queries for all cache-based approaches in both
datasets considering the default setup with $4$GB cache).

Table 3. Experimental parameters. Parameter | Range of values
---|---
Cache size (MB) | $1024,2048,\bm{4096},8128,16256$
Dataset size (core entity nodes) | $\bm{60\%},80\%,100\%$
Session restart probability | $0.04,0.06,\bm{0.08},0.1,0.12$
Workload distribution |  Uniform, Zipfian

All experiments ran on an AMD Ryzen Threadripper 3960X CPU machine @ 3.50GHz
with $256$GB RAM on Ubuntu 20.04 LTS. All considered approaches were able to
utilise all the available memory. Specifically, the Neo4j approach runs on the
Neo4j 4.2.5 Community Edition, configured to allocate $31$GB of JVM heap size
and $205$GB of page size, as
recommended.151515https://neo4j.com/docs/operations-
manual/current/tools/neo4j-admin-memrec/ The remaining memory can be allocated
by Neo4j from the OS (native memory) hence all $256$GB of memory could be
utilised in total (alternative configurations had no significant impact on
performance). In addition, Atrapos and its competitors load data from CSV
files into the main memory; this ingestion time is not included in the
reported query execution time. Table 3 lists the parameters we investigate and
the range of values for each parameter, with default values in bold.

###  4.2. Evaluation against single-query methods

First, we assess Atrapos against the dense-matrix HRank and Neo4j, using
subsets of the Scholarly HIN ($37k$ nodes, $120k$ edges) and the News articles
HIN ($37k$ nodes, $210k$ edges), as HRank and Neo4j cannot handle the full
datasets due to their memory requirements. Figure 7(a) presents our results on
execution time per query in logarithmic scale. Atrapos surpasses contestants
on both datasets. Neo4j is over one order of magnitude slower than Atrapos,
while HRank is over two orders of magnitude slower than Neo4j.

Then, we examine Atrapos against HRank-S, using full size HINs; HRank-S is a
variant of HRank that takes advantage of sparse matrix representations. Both
Atrapos and HRank-S use the same sparse matrix representations and the
respective multiplication cost estimation described in Section 3.2. However,
Atrapos leverages metapath query overlaps using a $4$GB cache. Figure 7(b)
presents our findings on execution time per query. Atrapos outperforms HRank-S
in both datasets with a speedup of $27\%$ on the Scholarly HIN and $23\%$ in
the News articles HIN.

###  4.3. Evaluation against baseline caching

While no existing approach exploits a caching mechanism to accelerate the
evaluation of a metapath query workload, evaluating Atrapos solely against
non-caching approaches cannot be fair. Thus, we introduce CBS1 and CBS2, two
HRank-S variants that employ basic caching mechanisms (Section 4.1) and assess
Atrapos against them. We include HRank-S in the same experiment for reference.
We first study performance vs. cache size and dataset size. Then, we
investigate workload parameters, i.e., the session restart probability $p$ and
the selection of metapaths and constraints.

(a) Vs. HRank & Neo4j
(dataset subsets, log scale).

(b) Vs. HRank-S (full dataset
sizes, linear scale)

Figure 7. Evaluation against single-query methods.

(a) Scholarly HIN

(b) News articles HIN

Figure 8. Evaluation against baseline caching approaches with varying cache
size.

####  4.3.1. Varying cache size.

Figure 8 presents the average execution time per query vs. cache size. As
HRank-S is oblivious to caching, its execution time is independent of cache
size. All cache-based approaches outperform HRank-S in both datasets, while
their advantage grows with cache size. CBS1 achieves faster times than HRank-S
by virtue of exploiting repetitive metapath queries; as it caches only query
results, it is slower than CBS2 and Atrapos. Atrapos outperforms other
contestants on both datasets, as it leverages the Overlap Tree to identify
frequent metapath overlaps and select matrix multiplication results for
caching. Its cache management policy refrains from inserting all intermediate
results into the cache, therefore its advantage over CBS2 is accentuated in
small cache sizes ($2$GB and $4$GB).

(a) Scholarly HIN

(b) News articles HIN

Figure 9. Evaluation against baseline caching approaches with varying dataset
size.

####  4.3.2. Varying dataset size.

Figure 9 illustrates the average execution time per query vs. network size.
The $x$ axis contains the number of edges (in millions) for each dataset split
(Section 4.1.1). All methods scale linearly with the number of edges. All
three cache-based approaches outperform HRank-S, with the difference being
more prominent in the Scholarly HIN. Atrapos clearly outperforms CBS1 and CBS2
on all dataset sizes.

(a) Scholarly HIN

(b) News articles HIN

Figure 10. Evaluation against baseline caching approaches varying session
restart probability.

####  4.3.3. Varying session restart probability $p$.

Figure 10 shows the improvement in execution time over HRank-S for CBS1, CBS2
and Atrapos as the session restart probability $p$ falls. As $p$ grows, the
performance of all cache-based methods degrades, as there are fewer queries
per session on average, hence fewer overlaps to exploit. Overall, Atrapos
outperforms its competitors. Among the rival methods, CBS2 surpasses CBS1, as
it exploits intermediate results.

(a) Scholarly HIN

(b) News articles HIN

Figure 11. Evaluation against baseline caching approaches with the queries
following the Zipf distribution.

####  4.3.4. Zipfian query workloads.

Figure 11 shows execution times per query as we vary the distribution from
which we select metapaths and constraints. Apart from the uniform
distribution, used in other experiments, we consider Zipfian distributions
varying the scaling parameter $\alpha$. HRank-S achieves comparable execution
times in all settings as it does not take advantage of repetitions, while
cache-based approaches improve as $\alpha$ grows. As $\alpha$ rises, the
probability of queries being repeated also increases, while smaller values
indicate a heavier tail in the probability distribution. Atrapos outperforms
competitors in all scenarios: it outperforms CBS1 by exploiting query overlaps
on top of the result that CBS1 caches. The difference is more notable with
$\alpha=1.2$ and $\alpha=1.6$, yet Atrapos surpasses CBS1 even with
$\alpha=2$, whereby a few queries are repeated in the workload. CBS2 exhibits
significantly larger execution times with Zipfian distributions, as caching
intermediate results bars it from exploiting all query repetitions.

(a) Scholarly HIN

(b) News articles HIN

Figure 12. Evaluation against baseline caching approaches considering
cumulative time per query.

(a) Scholarly HIN

(b) News articles HIN

(c) Scholarly HIN

(d) News articles HIN

Figure 13. Evaluation against baseline caching approaches considering query
execution time skewness.

####  4.3.5. Execution time per query

In our previous experiments, we presented the average execution time per query
across all query workloads. Here, we investigate the performance of individual
queries, averaging the reported execution times by query position across $10$
workflows. Figure 12 shows the cumulative time during workload execution;
cache-based approaches are noticeably faster than HRank-S, especially for the
Scholarly HIN. Atrapos is also considerably faster than CBS1 and CBS2 with the
difference increasing with the number of queries. Then, we investigate the
skewness of the query execution times for the same workloads. Specifically,
Figures 13a-b illustrate the execution time per query; it is highlighted that
Atrapos achieves considerable gains in some of the slower queries. Figures
13c-d reconfirm previous findings as each quartile of Atrapos starts lower
than the respective ones of the competitor approaches in both box plots.

###  4.4. Effect of cache replacement policies

We now benchmark our cache replacement policy against the Least Recently Used
(LRU) (Aho et al., 1971) and Popularity-aware Greedy Dual-Size (PGDS) (Shudong
Jin and Bestavros, 2000) policies (Section 3.4). We examine performance under
varying cache size (Section 4.4.1), dataset size (Section 4.4.2), session
restart probability $p$ (Section 4.4.3) and distributions for selecting
metapath queries (Section 4.4.4). All methods utilise the Overlap Tree to
identify query overlaps; their difference lies solely in the underlying cache
replacement policy.

(a) Scholarly HIN

(b) News articles HIN

Figure 14. Evaluation against cache replacement policies with varying cache
size.

####  4.4.1. Varying cache size.

Figure 14 shows our findings with varying cache size. Standard Atrapos
outperforms PGDS, the best performer among the rest on most scenarios; its
advantage is more prominent on Scholarly HIN. Yet, Atrapos is marginally
faster than the PGDS policy on News articles HIN; the most notable difference
appears with cache size equal to $8$GB; at the same time, both cache policies
incorporating frequency and item size outperform LRU.

(a) Scholarly HIN

(b) News articles HIN

Figure 15. Evaluation against cache replacement policies with varying dataset
size.

####  4.4.2. Varying dataset size.

Figure 15 presents our results for all policies as we vary the dataset size.
We observe a linear increase in execution time per query for all approaches as
dataset size grows. LRU performs poorly compared to the other approaches in
both datasets. Atrapos is faster than PGDS in most examined settings; it is
marginally faster in the Scholarly HIN, with performance gains being more
apparent when using the full News articles HIN dataset that comprises $298.11$
million edges.

(a) Scholarly HIN

(b) News articles HIN

Figure 16. Evaluation against cache replacement policies varying session
restart probability.

####  4.4.3. Varying session restart probability $p$

Figure 16 presents performance when varying the session restart probability
$p$. The speedup falls for all methods as $p$ grows, which is reasonable, as a
larger $p$ results in sessions containing fewer queries and thus fewer
overlaps to exploit. Atrapos attains larger gains than other contestants in
most examined configurations. More noteworthy differences appear on the
Scholarly HIN, especially for $p$ equal to $0.04$, $0.06$ and $0.08$. In the
News articles HIN, Atrapos is faster for small values of $p$ i.e. $0.04$ and
$0.06$, while PGDS achieves comparable results with Atrapos for larger $p$.
Both of them outperform LRU, with significant differences in both datasets.

(a) Scholarly HIN

(b) News articles HIN

Figure 17. Evaluation against cache replacement policies with the queries
following the Zipf distribution.

####  4.4.4. Zipfian query workloads.

Figure 17 illustrates the performance of the examined cache replacement
policies while using a Zipfian distribution for query workload generation. We
observe a notable performance improvement with all approaches when generating
the query workload by a Zipfian distribution compared to that when using a
uniform distribution. Moreover, as parameter $\alpha$ of the Zipfian
distribution grows, the gains for all methods become more prominent. A larger
$\alpha$ indicates a higher probability for query repetitions in the workload.
PGDS and Atrapos achieve comparable results on both datasets, with Atrapos
being marginally faster with the uniform distribution and the Zipfian with
$\alpha$ equal to $1.6$ and $2$ on the Scholarly HIN. Still, both of these
approaches outperform the LRU on both datasets.

(a) Scholarly HIN

(b) News articles HIN

Figure 18. Evaluation against cache replacement policies considering
cumulative time per query.

(a) Scholarly HIN

(b) News articles HIN

(c) Scholarly HIN

(d) News articles HIN

Figure 19. Evaluation against cache replacement policies considering query
execution time skewness.

####  4.4.5. Execution time per query.

Figure 18 shows the cumulative times for the different cache replacement
policies during workload execution. Atrapos and PGDS achieve comparable times,
yet Atrapos is slightly faster on the Scholarly HIN, as evident in Figure 18a.
LRU is slower than its competitors in both datasets; the difference is visible
in the second half of both query workload executions. Figures 19a-b plot the
execution time of each metapath query for the same workloads. We discern some
slower queries in the Scholarly HIN (Figure 19a) in which LRU achieves
considerably higher execution times that the other two approaches. Last but
not least, Figures 19c reconfirms that PGDS and Atrapos are faster than the
LRU as each quartile in their box plots starts lower than the respective
quartile for LRU for the Scholarly HIN. Of course, all considered approaches
in this section utilise the Overlap Tree, differing only in terms of the cache
replacement policy. Therefore, the difference in performance is small,
confirming what someone would expect.

##  5\. Related Work

Here, we review related work in HIN analysis, metapath query evaluation,
multi-query optimisation, and cache replacement.

###  5.1. HIN analysis

Heterogeneous information networks (HINs) are subject to growing attention, as
they afford a convenient model to represent information in several domains.
Metapaths are instrumental in many data mining tasks in HINs and are widely
used to capture complex semantics among HIN nodes. Several works rank HIN
nodes based on their centrality in a metapath-defined network (Ng et al.,
2011; Li et al., 2014; Lee et al., 2012). HRank (Shi et al., 2016a) co-ranks
HIN nodes and relations based on the intuition that important nodes are
connected to other nodes through important relations. Other works propose
metapath-based similarity measures among HIN nodes that encode different
similarity semantics and are used in a variety of similarity search and join
scenarios (Sun et al., 2011; Shi et al., 2014a, 2012; Y. Xiong, 2014). As
different metapaths reveal different associations among HIN nodes, recent
works incorporate metapath-based connectivity in link prediction and
recommendation HIN analysis tasks (Cao et al., 2014; Chen et al., 2018; Shi et
al., 2019). Furthermore, several community detection algorithms have been
proposed for HINs; some approaches detect clusters that contain nodes of
different types (Shi et al., 2014b; Sun et al., 2012a; Sun et al., 2009b),
while others generate homogeneous clusters (Sun et al., 2009a, 2013; Zhou and
Liu, 2013). In particular, Pathselclus (Sun et al., 2009a) uses user-defined
metapaths as seeds and automatically adjusts their weights during the
clustering process. As community detection algorithms take long time to form
all communities for large networks, (Fang et al., 2020) detects the community
of a given node in a HIN extending traditional metrics for community
cohesiveness to take metapaths into acccount.

###  5.2. Metapath query evaluation

A recent line of work focuses on metapath query evaluation. Shi et al. (Shi et
al., 2016a) apply dynamic programming (Cormen et al., 2009) to reorganize the
order of matrix multiplications required for metapath query evaluation,
thereby reducing computational cost. When small errors can be tolerated,
truncation strategies (Chakrabarti, 2007; Lao and Cohen, 2010) can be applied
in each step of matrix multiplication, zeroing values below a certain
threshold. Another approach follows a Monte Carlo strategy (Liu, 2008) to
approximate the query result via random walkers; the number of which strikes a
balance in the tradeoff between accuracy and computation cost. Unlike Atrapos,
these techniques focus on the performance of single-query evaluation,
incognizant of data exploration workloads with naturally emerging overlapping
queries. Finally, Sun et al. (Sun et al., 2011) propose the offline
materialisation of short metapaths in a preprocessing stage and concatenate
them at query time to make the online evaluation of a single query more
efficient.

###  5.3. Multi-query optimisation

Multi-query optimisation (MQO) has been heavily studied, in particular for
relational databases (Finkelstein, 1982; Sellis, 1988; Sellis and Ghosh, 1990;
Roy et al., 2000; Kathuria and Sudarshan, 2017). These works generate a
globally optimal plan by computing common sub-expressions within query batches
once and reuse them. In addition, MQO techniques have also been introduced in
structural graph pattern search using graph isomorphism (Ren and Wang, 2016).
Although these works share the same principles as Atrapos, they do not focus
on HINs while they greatly differ assuming queries are evaluated in batches;
this requires that query workloads are known a priori to determine common
computations across queries, which is not the case in real-time applications.
Atrapos, on the other hand, identifies query overlaps in real-time and
automatically caches the respective results if it is beneficial (according to
their occurrence frequency and their utility for the evaluation of other
queries). Lastly, MQO techniques for RDF-triple stores have been proposed
(Papailiou et al., 2015; Madkour et al., 2018). However, apart from the fact
that RDF graphs are less compact than HINs and hence likely to result in
increased memory footprint and execution times, such works consider _graph
pattern queries_ rather than metapaths; thus, Atrapos is customized for
metapath-based HIN analysis.

###  5.4. Cache replacement policies

There is a vast literature on cache replacement, especially in web server
caching (Podlipnig and Böszörmenyi, 2003; Balamash and Krunz, 2004). Much of
that work follows the Least Recently Used (LRU) policy (Aho et al., 1971);
LRU-MIN (Abrams et al., 1995) favors retaining smaller items in the cache,
while LRU-S (Starobinski and Tse, 2001) incorporates the size of cached items
into a randomized caching mechanism. Size-adjusted LRU (SLRU)(Aggarwal et al.,
1999), considers both the size and cost of cached items. Greedy Dual-based
approaches (Young, 1994; Cao and Irani, 1997) form another class of cache
replacement policies. Notably, Popularity-aware GreedyDual-Size (PGDS)
(Shudong Jin and Bestavros, 2000) utilizes the frequency, size, and cost of
cached items. GreedyDual* (GD*) (Jin and Bestavros, 2001) adaptively adjusts
the significance of _recency_ and _frequency_ information over time. Other
policies take into consideration the size and frequency of cached items (Rizzo
and Vicisano, 2000; Foong et al., 1999; Shim et al., 1999). An interesting
approach (Bahn et al., 2002) balances the recency and frequency of cached
items with different costs with the help of a user-defined parameter.
Nevertheless, none of the aforementioned policies considers the
_interdependence_ among cached items that inevitably appears in a metapath
query workload, as Atrapos does.

##  6\. Conclusions

We introduced Atrapos, a method to evaluate metapath query workloads in
semantic knowledge graph and heterogeneous information network analysis tasks
that exploits overlaps among query patterns. Atrapos accelerates metapath
computations using matrix multiplication algorithms tailored for sparse
matrices along with an appropriate cost model. Furthermore, it introduces an
overlap-aware cache replacement policy leveraging a tailor-made data
structure, the _Overlap Tree_ , that identifies overlapping metapaths among
queries. Our thorough experimental evaluation on two large real-world HINs
shows that Atrapos outperforms existing approaches in efficiency across all
examined scenarios.

## References

  * (1)
  * Abrams et al. (1995) Marc Abrams, Charles R Standridge, Ghaleb Abdulla, Stephen Williams, and Edward A Fox. 1995\.  _Caching proxies: Limitations and potentials_.  Technical Report. Department of Computer Science, Virginia Polytechnic Institute & State.
  * Aggarwal et al. (1999) Charu Aggarwal, Joel L Wolf, and Philip S. Yu. 1999\.  Caching on the world wide web.  _TKDE_ 11, 1 (1999), 94–107.
  * Aho et al. (1971) Alfred V Aho, Peter J Denning, and Jeffrey D Ullman. 1971\.  Principles of optimal page replacement.  _JACM_ 18, 1 (1971), 80–93.
  * Asay ([n.d.]) Matt Asay. [n.d.].  _Neo4j’s $325 million venture suggests databases are cool again_.  https://www.techrepublic.com/article/neo4js-325-million-venture-suggests-databases-are-cool-again/
  * Bahn et al. (2002) Hyokyung Bahn, Kern Koh, Sam H Noh, and SM Lyul. 2002\.  Efficient replacement of nonuniform objects in web caches.  _Computer_ 35, 6 (2002), 65–73.
  * Balamash and Krunz (2004) Abdullah Balamash and Marwan Krunz. 2004.  An overview of web caching replacement algorithms.  _IEEE Communications Surveys & Tutorials_ 6, 2 (2004), 44–56.
  * Bieganski et al. (1994) Paul Bieganski, John Riedl, John V Carlis, and Ernest F Retzel. 1994.  Generalized suffix trees for biological sequence data: applications and implementation. In _HICSS_. 35–44.
  * Cao et al. (2014) Bokai Cao, Xiangnan Kong, and Philip S. Yu. 2014.  Collective Prediction of Multiple Types of Links in Heterogeneous Information Networks. In _ICDM_. 50–59.
  * Cao and Irani (1997) Pei Cao and Sandy Irani. 1997.  Cost-aware www proxy caching algorithms.. In _Usenix_ , Vol. 12. 193–206.
  * Chakrabarti (2007) Soumen Chakrabarti. 2007\.  Dynamic personalized pagerank in entity-relation graphs. In _WWW_. 571–580.
  * Chatzopoulos et al. (2020) Serafeim Chatzopoulos, Kostas Patroumpas, Alexandros Zeakis, Thanasis Vergoulis, and Dimitrios Skoutas. 2020.  SPHINX: a system for metapath-based entity exploration in heterogeneous information networks.  _VLDB_ 13, 12 (2020), 2913–2916.
  * Chatzopoulos et al. (2021) Serafeim Chatzopoulos, Thanasis Vergoulis, Panagiotis Deligiannis, Dimitrios Skoutas, Theodore Dalamagas, and Christos Tryfonopoulos. 2021\.  SciNeM: A Scalable Data Science Tool for Heterogeneous Network Mining.. In _EDBT_. 654–657.
  * Chen et al. (2018) Hongxu Chen, Hongzhi Yin, Weiqing Wang, Hao Wang, Quoc Viet Hung Nguyen, and Xue Li. 2018\.  PME: Projected Metric Embedding on Heterogeneous Networks for Link Prediction. In _SIGKDD_. 1177–1186.
  * Chen et al. (2021) Hsi-Wen Chen, Hong-Han Shuai, De-Nian Yang, Wang-Chien Lee, Chuan Shi, S Yu Philip, and Ming-Syan Chen. 2021.  Structure-Aware Parameter-Free Group Query via Heterogeneous Information Network Transformer. In _ICDE_. 2075–2080.
  * Cohen (1998) Edith Cohen. 1998\.  Structure Prediction and Computation of Sparse Matrix Products.  _Journal of Combinatorial Optimization_ 2, 4 (1998), 307–332.
  * Cormen et al. (2009) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009.  _Introduction to Algorithms, 3rd Edition_.  MIT Press.  http://mitpress.mit.edu/books/introduction-algorithms
  * Fang et al. (2021) Yixiang Fang, Kai Wang, Xuemin Lin, and Wenjie Zhang. 2021\.  Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions. In _SIGMOD_. 2829–2838.
  * Fang et al. (2020) Yixiang Fang, Yixing Yang, Wenjie Zhang, Xuemin Lin, and Xin Cao. 2020.  Effective and efficient community search over large heterogeneous information networks.  _VLDB_ 13, 6 (2020), 854–867.
  * Finkelstein (1982) Sheldon Finkelstein. 1982\.  Common expression analysis in database applications. In _SIGMOD_. 235–245.
  * Foong et al. (1999) Annie P Foong, Yu-Hen Hu, and Dennis M Heisey. 1999.  Adaptive web caching using logistic regression. In _SSP_. 515–524.
  * Guennebaud et al. (2010) Gaël Guennebaud, Benoît Jacob, et al. 2010\.  Eigen v3.  http://eigen.tuxfamily.org.
  * Jian et al. (2020) Xun Jian, Yue Wang, and Lei Chen. 2020.  Effective and efficient relational community detection and search in large dynamic heterogeneous information networks.  _VLDB_ 13, 10 (2020), 1723–1736.
  * Jin and Bestavros (2001) Shudong Jin and Azer Bestavros. 2001.  GreedyDual* Web caching algorithm: exploiting the two sources of temporal locality in Web request streams.  _Computer Communications_ 24, 2 (2001), 174–183.
  * Kathuria and Sudarshan (2017) Tarun Kathuria and S Sudarshan. 2017.  Efficient and provable multi-query optimization. In _Symposium on Principles of Database Systems (ACM SIGMOD-SIGACT-SIGAI)_. 53–67.
  * Kernert et al. (2015) David Kernert, Frank Köhler, and Wolfgang Lehner. 2015\.  SpMacho - Optimizing Sparse Linear Algebra Expressions with Probabilistic Density Estimation. In _EDBT_.
  * Lao and Cohen (2010) Ni Lao and William W Cohen. 2010.  Fast query execution for retrieval models based on path-constrained random walks. In _SIGKDD_. 881–888.
  * Lee et al. (2012) Sangkeun Lee, Sungchan Park, Minsuk Kahng, and Sang Goo Lee. 2012\.  PathRank: a novel node ranking measure on a heterogeneous graph for recommender systems.  _CIKM_.
  * Leetaru and Schrodt (2013) Kalev Leetaru and Philip A Schrodt. 2013.  Gdelt: Global data on events, location, and tone, 1979–2012. In _ISA annual convention_ , Vol. 2. Citeseer, 1–49.
  * Li et al. (2021) Xiang Li, Danhao Ding, Ben Kao, Yizhou Sun, and Nikos Mamoulis. 2021.  Leveraging Meta-path Contexts for Classification in Heterogeneous Information Networks. In _ICDE_. 912–923.
  * Li et al. (2014) Yitong Li, Chuan Shi, S Yu Philip, and Qing Chen. 2014\.  Hrank: a path based ranking method in heterogeneous information network. In _WAIM_. 553–565.
  * Liu (2008) Jun S Liu. 2008\.  _Monte Carlo strategies in scientific computing_.  Springer Science & Business Media.
  * Madkour et al. (2018) Amgad Madkour, Ahmed M Aly, and Walid G Aref. 2018.  Worq: Workload-driven rdf query processing. In _International Semantic Web Conference (ISWC)_. 583–599.
  * Meng et al. (2015) Changping Meng, Reynold Cheng, Silviu Maniu, Pierre Senellart, and Wangda Zhang. 2015.  Discovering Meta-Paths in Large Heterogeneous Information Networks. In _WWW_. 754–764.
  * Neumann and Weikum (2010) Thomas Neumann and Gerhard Weikum. 2010.  The RDF-3X engine for scalable management of RDF data.  _VLDB_ 19, 1 (2010), 91–113.
  * Ng et al. (2011) Michaek Kwok-Po Ng, Xutao Li, and Yunming Ye. 2011.  Multirank: co-ranking for objects and relations in multi-relational data. In _SIGKDD_. 1217–1225.
  * Papailiou et al. (2015) Nikolaos Papailiou, Dimitrios Tsoumakos, Panagiotis Karras, and Nectarios Koziris. 2015.  Graph-aware, workload-adaptive SPARQL query caching. In _SIGMOD_. 1777–1792.
  * Podlipnig and Böszörmenyi (2003) Stefan Podlipnig and Laszlo Böszörmenyi. 2003\.  A survey of web cache replacement strategies.  _CSUR_ 35, 4 (2003), 374–398.
  * Ren and Wang (2016) Xuguang Ren and Junhu Wang. 2016.  Multi-query optimization for subgraph isomorphism search.  _VLDB_ 10, 3 (2016), 121–132.
  * Rizzo and Vicisano (2000) Luigi Rizzo and Lorenzo Vicisano. 2000.  Replacement policies for a proxy cache.  _IEEE/ACM Transactions on Networking_ 8, 2 (2000), 158–170.
  * Roy et al. (2000) Prasan Roy, Srinivasan Seshadri, S Sudarshan, and Siddhesh Bhobe. 2000.  Efficient and extensible algorithms for multi query optimization. In _SIGMOD_. 249–260.
  * Sellis and Ghosh (1990) Timos Sellis and Subrata Ghosh. 1990.  On the multiple-query optimization problem.  _Transactions on Knowledge and Data Engineering (TKDE)_ 2, 02 (1990), 262–266.
  * Sellis (1988) Timos K Sellis. 1988\.  Multiple-query optimization.  _TODS_ 13, 1 (1988), 23–52.
  * Shen et al. (2014) Wei Shen, Jiawei Han, and Jianyong Wang. 2014.  A probabilistic model for linking named entities in web text with heterogeneous information networks. In _SIGMOD_. 1199–1210.
  * Shi and Weninger (2014) Baoxu Shi and Tim Weninger. 2014.  Mining Interesting Meta-Paths from Complex Heterogeneous Information Networks. In _ICDM_. 488–495.
  * Shi et al. (2019) Chuan Shi, Binbin Hu, Wayne Xin Zhao, and Philip S. Yu. 2019\.  Heterogeneous Information Network Embedding for Recommendation.  _TKDE_ 31, 2 (2019), 357–370.
  * Shi et al. (2014a) Chuan Shi, Xiangnan Kong, Yue Huang, S Yu Philip, and Bin Wu. 2014a.  Hetesim: A general framework for relevance measure in heterogeneous networks.  _TKDE_ 26, 10 (2014), 2479–2492.
  * Shi et al. (2012) Chuan Shi, Xiangnan Kong, Philip S Yu, Sihong Xie, and Bin Wu. 2012.  Relevance search in heterogeneous networks. In _EDBT_. 180–191.
  * Shi et al. (2016a) Chuan Shi, Yitong Li, Philip S. Yu, and Bin Wu. 2016a.  Constrained-meta-path-based ranking in heterogeneous information network.  _Knowledge and Information Systems_ 49, 2 (2016), 719–747.
  * Shi et al. (2016b) Chuan Shi, Yitong Li, Jiawei Zhang, Yizhou Sun, and S Yu Philip. 2016b.  A survey of heterogeneous information network analysis.  _TKDE_ 29, 1 (2016), 17–37.
  * Shi et al. (2014b) Chuan Shi, Ran Wang, Yitong Li, Philip S Yu, and Bin Wu. 2014b.  Ranking-based clustering on general heterogeneous information networks by network projection. In _CIKM_. 699–708.
  * Shim et al. (1999) Junho Shim, Peter Scheuermann, and Radek Vingralek. 1999\.  Proxy cache algorithms: Design, implementation, and performance.  _TKDE_ 11, 4 (1999), 549–562.
  * Shudong Jin and Bestavros (2000) Shudong Jin and A. Bestavros. 2000.  Popularity-aware greedy dual-size Web proxy caching algorithms. In _ICDCS_. 254–261.
  * Sommer et al. (2019) Johanna Sommer, Matthias Boehm, Alexandre V. Evfimievski, Berthold Reinwald, and Peter J. Haas. 2019\.  MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions. In _SIGMOD_. 1607–1623.
  * Starobinski and Tse (2001) David Starobinski and David Tse. 2001.  Probabilistic methods for web caching.  _Performance Evaluation_ 46, 2-3 (2001), 125–137.
  * Sun et al. (2012a) Yizhou Sun, Charu C Aggarwal, and Jiawei Han. 2012a.  Relation strength-aware clustering of heterogeneous information networks with incomplete attributes.  _arXiv preprint arXiv:1201.6563_ (2012).
  * Sun et al. (2012b) Yizhou Sun, Jiawei Han, Xifeng Yan, and Philip S Yu. 2012b.  Mining knowledge from interconnected data: a heterogeneous information network analysis approach.  _VLDB_ 5, 12 (2012), 2022–2023.
  * Sun et al. (2011) Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. 2011.  PathSim: Meta Path-Based Top-$k$ Similarity Search in Heterogeneous Information Networks.  _PVLDB_ 4, 11 (2011), 992–1003.
  * Sun et al. (2009a) Yizhou Sun, Jiawei Han, Peixiang Zhao, Zhijun Yin, Hong Cheng, and Tianyi Wu. 2009a.  Rankclus: integrating clustering with ranking for heterogeneous information network analysis. In _EDBT_. 565–576.
  * Sun et al. (2013) Yizhou Sun, Brandon Norick, Jiawei Han, Xifeng Yan, Philip S Yu, and Xiao Yu. 2013\.  Pathselclus: Integrating meta-path selection with user-guided object clustering in heterogeneous information networks.  _TKDD_ 7, 3 (2013), 1–23.
  * Sun et al. (2009b) Yizhou Sun, Yintao Yu, and Jiawei Han. 2009b.  Ranking-based clustering of heterogeneous information networks with star network schema. In _SIGKDD_. 797–806.
  * Szpankowski (1993) Wojciech Szpankowski. 1993\.  A generalized suffix tree and its (un) expected asymptotic behaviors.  _SICOMP_ 22, 6 (1993), 1176–1198.
  * Tang et al. (2008) Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008.  ArnetMiner: Extraction and Mining of Academic Social Networks. In _SIGKDD_. 990–998.
  * Ukkonen (1995) Esko Ukkonen. 1995\.  On-line construction of suffix trees.  _Algorithmica_ 14, 3 (1995), 249–260.
  * Wang et al. (2020) Yue Wang, Zhe Wang, Ziyuan Zhao, Zijian Li, Xun Jian, Lei Chen, and Jianchun Song. 2020.  HowSim: A General and Effective Similarity Measure on Heterogeneous Information Networks. In _ICDE_. 1954–1957.
  * Webber (2012) Jim Webber. 2012\.  A programmatic introduction to neo4j. In _SPLASH_. 217–218.
  * Weiss et al. (2008) Cathrin Weiss, Panagiotis Karras, and Abraham Bernstein. 2008\.  Hexastore: sextuple indexing for semantic web data management.  _VLDB_ 1, 1 (2008), 1008–1019.
  * Xie et al. (2021) Tao Xie, Yangjun Xu, Liang Chen, Yang Liu, and Zibin Zheng. 2021.  Sequential Recommendation on Dynamic Heterogeneous Information Network. In _ICDE_. 2105–2110.
  * Y. Xiong (2014) P. Yu Y. Xiong, Y. Zhu. 2014\.  Top-k Similarity Join in Heterogeneous Information Networks.  _TKDE_ 27, 6 (2014), 1710–1723.
  * Yang et al. (2020) Yixing Yang, Yixiang Fang, Xuemin Lin, and Wenjie Zhang. 2020\.  Effective and efficient truss computation over large heterogeneous information networks. In _ICDE_. 901–912.
  * Young (1994) Neal Young. 1994\.  Thek-server dual and loose competitiveness for paging.  _Algorithmica_ 11, 6 (1994), 525–541.
  * Yu et al. (2017) Yongyang Yu, Mingjie Tang, Walid G. Aref, Qutaibah M. Malluhi, Mostafa Abbas, and Mourad Ouzzani. 2017.  In-memory distributed matrix computation processing & optimization. In _ICDE_. 1047–1058.
  * Zhou and Liu (2013) Yang Zhou and Ling Liu. 2013.  Social influence based clustering of heterogeneous information networks. In _SIGKDD_. 338–346.