Chao Zhang
email: chao.zhang@univ-lyon1.fr

Angela Bonifati
email: angela.bonifati@univ-lyon1.fr

Hugo Kapp
email: hugo.kapp@oracle.com

Vlad Ioan Haprian
email: vlad.haprian@oracle.com

Jean-Pierre Lozi
email: jean-pierre.lozi@inria.fr

A Reachability Index for Recursive Label-Concatenated Graph Queries

Keywords: reachability index, graph query, graph databases, RLC queries

Reachability queries checking the existence of a path from a source node to a target node are fundamental operators for querying and processing graph data. Current approaches for index-based evaluation of reachability queries either focus on plain reachability or constraint-based reachability with the alternation of edge labels only. In this paper, we study for the first time the problem of index-based processing for recursive labelconcatenated reachability queries, referred to as RLC queries. These queries check the existence of a path that can satisfy the constraint defined by a concatenation of at most k edge labels under the Kleene plus. Many practical graph database and network analysis applications exhibit RLC queries. However, their evaluation remains prohibitive in current graph database engines.

We introduce the RLC index, the first reachability index to efficiently process RLC queries. The RLC index checks whether the source vertex can reach an intermediate vertex that can also reach the target vertex under a recursive label-concatenated constraint. We propose an indexing algorithm to build the RLC index, which guarantees the soundness and the completeness of query execution and avoids recording redundant index entries. Comprehensive experiments on real-world graphs show that the RLC index can significantly reduce both the offline processing cost and the memory overhead of computing and storing transitive closure, while improving query processing up to six orders of magnitude over online traversals. Finally, our open-source implementation of the RLC index significantly outperforms current mainstream graph engines for evaluating RLC queries.

I. INTRODUCTION

Graphs have been the natural choice of data representation in various domains [START_REF] Newman | Networks: An Introduction[END_REF], e.g., social, biochemical, fraud detection and transportation networks, and reachability queries are fundamental graph operators [START_REF] Sahu | The ubiquity of large graphs and surprising challenges of graph processing[END_REF]. Plain reachability queries check whether there exists a path from a source vertex to a target vertex, for which various indexing techniques have been proposed [START_REF] Agrawal | Efficient management of transitive relationships in large data and knowledge bases[END_REF]- [START_REF] Yano | Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[END_REF]. To facilitate the representation of different types of relationships in real-world applications, edge-labeled graphs and property graphs, where labels can be assigned to edges, are more widely adopted nowadays than unlabeled graphs. Such advanced graph models allow users to add path constraints when defining reachability queries, which play a key role in graph analytics. However, current indexbased approaches focus on constraint-based reachability with § Work completed while at Oracle Labs.

alternation only [START_REF] Jin | Computing label-constraint reachability in graph databases[END_REF]- [START_REF] Chen | Graph indexing for efficient evaluation of label-constrained reachability queries[END_REF]. In this paper, for the first time, we consider reachability queries with a complex path constraint corresponding to a concatenation of edge labels under the Kleene plus, referred to as recursive label-concatenated queries (RLC queries). RLC queries are a prominent subset of regular path queries, for which indexing techniques have not been understood yet. As such, they are significant counterparts of queries with the alternation of edge labels as path constraints [START_REF] Valstar | Landmark indexing for evaluation of label-constrained reachability queries[END_REF] and queries without path constraints, i.e., plain reachability queries [START_REF] Agrawal | Efficient management of transitive relationships in large data and knowledge bases[END_REF]. We further motivate RLC queries by means of a running example.

Example 1: Figure 1 shows a property graph inspired by a real-world use case which encodes an interleaved social and professional network along with information on bank accounts of persons. RLC queries can be used to detect fraud and money laundering patterns among financial transactions. For instance, the query Q1(A 14 , A 19 , (debits, credits) + ) checks whether there is a path from account A 14 to A 19 such that the label sequence of the path is a concatenation of an arbitrary number of occurrences of (debits, credits), which can lead to detect suspicious patterns of money transfers between these accounts. The RLC query Q1((A 14 , A 19 , (debits, credits) + ) evaluates to true because of the existence of the path (A 14 , debits, E 15 , credits, A 17 , debits, E 18 , credits, A 19 ). Another example is Q2(P 10 , P 13 , (knows, knows, worksFor) + ) that evaluates to false because there is no path from P 10 to P 13 satisfying the constraint.

RLC queries are also frequently occurring in real-world query logs, e.g., Wikidata Query Logs [START_REF] Bonifati | Navigating the maze of wikidata query logs[END_REF], which is the largest repository of open-source graph queries (of the order of 500M queries). In particular, RLC queries often timed out in these logs [START_REF] Bonifati | Navigating the maze of wikidata query logs[END_REF], thus showing the limitations of graph query engines to efficiently evaluate them. Moreover, Neo4j (v4.3) [START_REF]Neo4j[END_REF] and TigerGraph (v3.3) [START_REF] Deutsch | TigerGraph: A native mpp graph database[END_REF], two of the mainstream graph data processing engines, do not yet support RLC queries in their current version. On the other hand, these systems have already identified the need to support these queries in the near future by following the developments of the Standard Graph Query Language (GQL) [START_REF]Graph query language gql standard[END_REF]. RLC queries can be expressed in Gremlin which is supported by TinkerPop-Enabled Graph Systems [START_REF]Apache TinkerPop data system providers[END_REF], e.g., Amazon Neptune [START_REF] Bebee | Amazon Neptune: Graph data management in the cloud[END_REF], in PGQL [START_REF] Van Rest | PGQl: A property graph query language[END_REF] supported which is by Oracle PGX [START_REF] Hong | PGX.D: A fast distributed graph processing engine[END_REF], [START_REF] Trigonakis | aDFS: An almost depth-first-search distributed graph-querying system[END_REF], and in SPARQL 1 Fig. 1. A social and professional network for illustrating RLC queries.

1.1 (ASK query) which is supported by Virtuoso [START_REF]Virtuoso[END_REF] and Apache Jena [START_REF]Apache Jena[END_REF], among others. However, many of these systems cannot efficiently evaluate RLC queries yet as shown in our experimental study.

To the best of our knowledge, little research has been carried out on an index-based solution to evaluate RLC queries, whereas indexing is a desirable asset of future graph processing systems that allows to improve and predict the performance of graph queries [START_REF] Sakr | The future is big graphs: A community view on graph processing systems[END_REF]. Previous plain reachability indexes have been well studied [START_REF] Agrawal | Efficient management of transitive relationships in large data and knowledge bases[END_REF]- [START_REF] Su | Reachability querying: Can it be even faster?[END_REF], but are not usable to evaluate RLC queries because of the lack of edge label information. More recent indexing methods have been focused on the alternation of edge labels [START_REF] Jin | Computing label-constraint reachability in graph databases[END_REF]- [START_REF] Chen | Graph indexing for efficient evaluation of label-constrained reachability queries[END_REF], instead of the concatenation of edge labels in RLC queries.

In this work, we propose the RLC index, the first reachability index tailored for RLC queries. In the RLC index, we assign pairs of vertices and succinct label sequences to each vertex. Then, the RLC index processes an RLC query by checking whether the source vertex can reach an intermediate vertex that can also reach the target vertex under the path constraint.

Challenge C1. One of the challenges for building an index to process RLC queries is that there can be infinite sequences of edge labels from vertex s to vertex t due to the presence of cycles on paths from s to t. Thus, building an index for arbitrary RLC queries can be hard since the number of label sequences for cyclic graphs is growing exponentially and potentially infinite, which leads to unrealistic indexing time and index size. We overcame this issue by leveraging a practical observation: the number of edge labels concatenated under the Kleene plus (or star) is typically bounded in realworld query logs, e.g., [START_REF] Bonifati | Navigating the maze of wikidata query logs[END_REF]. We refer to the maximum number of concatenated labels in a workload of RLC queries as recursive k. Given an arbitrary recursive k, we show that the RLC index can be built correctly to evaluate any RLC query with a recursive concatenation of at most k arbitrary edge labels. Note that recursive k only depends on the number of concatenated labels and not on the actual length of any path selected by RLC queries.

Challenge C2. Although abundant indexing algorithms [3]- [START_REF] Yano | Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[END_REF] have been proposed for plain reachability, which were then extended to alternation-based reachability queries [START_REF] Jin | Computing label-constraint reachability in graph databases[END_REF]- [START_REF] Chen | Graph indexing for efficient evaluation of label-constrained reachability queries[END_REF], none of them is able to build an index for RLC queries because of the completely different path constraints. More precisely, indexing reachability with recursive concatenationbased path-constraints requires recording sequences of edge labels. However, indexing reachability with alternation-based path-constraints requires sets of edge labels, or plain reacha-bility without edge labels. Such a fundamental difference illustrates the hardness of the problem and shows the inadequacy of existing indexing algorithms to build the RLC index. We design a novel indexing algorithm that builds the RLC index efficiently over large and highly cyclic graphs with millions of vertices and edges, as shown in our experiments. The indexing algorithm searches and records paths with recursive concatenation-based constraints, and during each searching step, identifies the condition that makes it possible to prune the search space and avoid recording redundant index entries.

Contribution. Our contributions are summarized as follows:

• We study the problem of indexing for RLC queries, i.e., reachability queries with a complex path constraint consisting of the Kleene plus over the concatenation of edge labels.

We propose a novel instantiation of the problem to address challenge C1. • We propose the RLC index, the first reachability index for processing RLC queries, along with its indexing algorithm to address challenge C2. We prove that the latter builds a sound and complete RLC index for an arbitrary recursive k, where redundant index entries can be greedily removed. • Our comprehensive experiments using highly cyclic realworld graphs show that the RLC index can be built efficiently and can significantly reduce the memory overhead of the (extended) transitive closure. Moreover, the RLC index is capable of answering RLC queries efficiently, up to six orders of magnitude faster than online traversals. We also demonstrate the speed-up and the generality of using the RLC index to accelerate query processing on mainstream graph engines. Our code is available as open source 1 . The rest of the paper is organized as follows. Section II presents the related work and Section III introduces the RLC queries. Section IV presents the theoretical foundation of our approach and Section V describes the RLC index and its indexing algorithm. Section VI presents the experimental assessment of executing RLC queries using the RLC index. Section VII concludes our work. All related proofs are included in our technical report [START_REF] Zhang | A reachability index for recursive label-concatenated graph queries[END_REF] due to the space constraint.

II. RELATED WORK

The two most fundamental graph queries [START_REF] Angles | Foundations of modern query languages for graph databases[END_REF] are graph pattern matching queries and regular path queries (aka navigational queries). The former matches a query graph against a graph database while the latter recursively navigates a graph according to a regular expression. The two fundamental queries are completely orthogonal, and RLC queries belong to the class of the latter. Thus, we discuss regular path queries and related indexes in this section. We note approaches [START_REF] Ullmann | An algorithm for subgraph isomorphism[END_REF]- [START_REF] Kim | Idar: Fast supergraph search using dag integration[END_REF] for efficiently evaluating graph pattern matching queries. We refer readers to surveys [START_REF] Lee | An in-depth comparison of subgraph isomorphism algorithms in graph databases[END_REF], [START_REF] Sun | In-memory subgraph matching: An in-depth study[END_REF]. We do not elaborate on them further and do not consider them in our experimental evaluation due to the completely different query types. Plain Reachability Index. Given an unlabeled graph G = (V, E) and a pair of vertices (s, t), a plain reachability query asks whether there exists a path from s to t. The existing approaches lie between two extremes, i.e., online traversals and the transitive closure. Various indexes have been proposed. Comprehensive surveys can be found in [START_REF] Su | Reachability querying: Can it be even faster?[END_REF], [START_REF] Yu | Graph reachability queries: A survey[END_REF], [START_REF] Bonifati | Querying Graphs[END_REF]. Plain reachability indexes mainly fall into two categories [START_REF] Wei | Reachability querying: An independent permutation labeling approach[END_REF], [START_REF] Su | Reachability querying: Can it be even faster?[END_REF]:

(1) index-only approaches, e.g., Chain Cover [START_REF] Jagadish | A compression technique to materialize transitive closure[END_REF], [START_REF] Chen | An efficient algorithm for answering graph reachability queries[END_REF], Tree Cover [START_REF] Agrawal | Efficient management of transitive relationships in large data and knowledge bases[END_REF], Dual Labeling [START_REF] Wang | Dual labeling: Answering graph reachability queries in constant time[END_REF], Path-Tree Cover [START_REF] Jin | Efficiently answering reachability queries on very large directed graphs[END_REF], 2-Hop labeling [START_REF] Cohen | Reachability and distance queries via 2-hop labels[END_REF], TFL [START_REF] Cheng | TF-Label: A topological-folding labeling scheme for reachability querying in a large graph[END_REF], TOL [START_REF] Zhu | Reachability queries on large dynamic graphs: A total order approach[END_REF], PLL [START_REF] Yano | Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[END_REF], 3-Hop labeling [START_REF] Jin | 3-HOP: A highcompression indexing scheme for reachability query[END_REF], among others; (2) index-with-graph-traversal approaches, such as Tree+SSPI [START_REF] Chen | Stack-based algorithms for pattern matching on dags[END_REF], GRIPP [START_REF] Trißl | Fast and practical indexing and querying of very large graphs[END_REF], GRAIL [START_REF] Yildirim | Grail: Scalable reachability index for large graphs[END_REF], Ferrari [START_REF] Seufert | Ferrari: Flexible and efficient reachability range assignment for graph indexing[END_REF], IP [START_REF] Wei | Reachability querying: An independent permutation labeling approach[END_REF], and BFL [START_REF] Su | Reachability querying: Can it be even faster?[END_REF].

RLC queries are different from plain reachability queries because they are evaluated on labeled graphs to find the existence of a path satisfying additional recursive labelconcatenated constraints. Thus, the indexes used to evaluate plain reachability queries, e.g., 2-hop labeling [START_REF] Cohen | Reachability and distance queries via 2-hop labels[END_REF], are not suitable for RLC queries. More precisely, indexing techniques for plain reachability queries only record information about graph structure but ignore information of edge labels. Alternation-Based Reachability Index. Reachability queries with a path constraint that is based on the alternation of edge labels (instead of concatenation as in our work), are known as LCR queries in the literature. Index-based solutions for LCR queries have been extensively studied in the last decade.

Jin et. al [START_REF] Jin | Computing label-constraint reachability in graph databases[END_REF] presented the first result on LCR queries. To compress the generalized transitive closure that records reachable pairs and sets of path-labels, the authors proposed sufficient label sets and a spanning tree with a partial transitive closure. The Zou et. al [START_REF] Zou | Efficient processing of label-constraint reachability queries in large graphs[END_REF] method finds all strongly connected components (SCCs) in an input graph and replaces each SCC with a bipartite graph to obtain an edge-labeled DAG. Valstar et. al [START_REF] Valstar | Landmark indexing for evaluation of label-constrained reachability queries[END_REF] proposed a landmark-based index, where the generalized transitive closure for a set of highdegree vertices called landmarks is built and an online traversal is applied to answer LCR queries, which is accelerated by hitting landmarks. The state-of-the-art indexing techniques for LCR queries are the Peng et. al [START_REF] Peng | Answering billion-scale label-constrained reachability queries within microsecond[END_REF] method and the Chen et. al [START_REF] Chen | Graph indexing for efficient evaluation of label-constrained reachability queries[END_REF] method. Peng et. al [START_REF] Peng | Answering billion-scale label-constrained reachability queries within microsecond[END_REF] proposed the LC 2-hop labeling, which extends the 2-hop labeling framework through adding minimal sets of path-labels for each entry in the 2hop labeling. Chen et. al [START_REF] Chen | Graph indexing for efficient evaluation of label-constrained reachability queries[END_REF] proposed a recursive method to handle LCR queries, where an input graph is recursively decomposed into spanning trees and graph summaries.

LCR queries and RLC queries have completely different regular expressions as path constraints, which makes the corresponding indexing problem inherently different. The expression in LCR queries is the alternation of edge labels, while the one in RLC queries is the concatenation of edge labels. The completely different path constraint makes LCR indexes inapplicable for processing RLC queries. The difference on path constraints also makes the indexing algorithms for LCR queries and RLC queries fundamentally different. For instance, for an LCR indexing algorithm, it is sufficient to traverse any cycle in a graph only once. Conversely, in the case of RLC queries, a cycle, especially a self loop, might need to be traversed multiple times depending on label sequences along paths. In a nutshell, indexing approaches for LCR queries are not applicable to indexing RLC queries. Regular Path Queries. Regular path queries correspond to queries generating node pairs according to path constraints specified using regular expressions. Under the simple path semantics (non-repeated vertices or edges in a path), it is NPcomplete to check the existence of a path satisfying a regular expression [START_REF] Mendelzon | Finding regular simple paths in graph databases[END_REF]. Thus, a recent work [START_REF] Wadhwa | Efficiently answering regular simple path queries on large labeled networks[END_REF] focused on an approximate solution for evaluating regular simple path queries. By restricting regular expressions or graph instances, there exist tractable cases [START_REF] Mendelzon | Finding regular simple paths in graph databases[END_REF], [START_REF] Bagan | A trichotomy for regular simple path queries on graphs[END_REF], including LCR queries but not RLC queries. When it comes to the arbitrary path semantics (allowing repeated vertices or edges in a path), regular path queries for generating node pairs can be processed by using automata-based techniques [START_REF] Wood | Query languages for graph databases[END_REF], [START_REF] Baeza | Querying graph databases[END_REF] or bi-directional BFSs from rare labels [START_REF] Koschmieder | Regular path queries on large graphs[END_REF]. Optimal solutions can be used for subclasses of regular expressions, e.g., a matrix-based method [START_REF] Fan | Adding regular expressions to graph reachability and pattern queries[END_REF] for the case without recursive concatenations, and a B+tree index for the case with a bounded path length (non-recursive path constraints) [START_REF] Fletcher | Efficient regular path query evaluation using path indexes[END_REF] and a fixed path pattern [START_REF] Kuijpers | Path indexing in the cypher query pipeline[END_REF]. There also exist in the literature partial evaluation for distributed graphs [START_REF] Fan | Performance guarantees for distributed reachability queries[END_REF], and incremental approaches for streaming graphs [START_REF] Pacaci | Regular path query evaluation on streaming graphs[END_REF], [START_REF] Pacaci | Evaluating complex queries on streaming graphs[END_REF]. Compared to all these works, we focus on designing an index-based solution to handle reachability queries with path constraints of recursive concatenations over a static and centralized graph under the arbitrary path semantics, which is an open challenge in the design of reachability indexes. To the best of our knowledge, our work is the first of its kind focusing on the design of a reachability index for such queries.

III. PROBLEM STATEMENT

An edge-labeled graph is G = (V, E, L), where L is a finite set of labels, V a finite set of vertices, and E ⊆ V × L × V a finite set of labeled edges. For the graph in Fig. 1, we have L = {knows, worksFor, debits, credits, holds}, and that e 1 =(P 10 , knows, P 11 ) is a labeled edge. We use λ : E → L to denote the mapping from an edge to its label, e.g., λ(e 1 ) = knows. The frequently used symbols are summarized in Table I.

In this paper, we consider the arbitrary path semantics [START_REF] Angles | Foundations of modern query languages for graph databases[END_REF] for evaluating RLC queries, i.e., vertices or edges can appear more than once along the path. The arbitrary path semantics is widely adopted in practical graph query languages, e.g., SPARQL 1.1 and PGQL, because evaluating a reachability query with an arbitrary regular expression as the path constraint is tractable under the arbitrary path semantics but is NPcomplete under the simple path semantics, e.g., RLC queries. It should be noteworthy that LCR queries with alternationbased path constraints belong to a special class (trC class [START_REF] Bagan | A trichotomy for regular simple path queries on graphs[END_REF]), which remains tractable under the simple path semantics.

An arbitrary path p in G is a vertex-edge alternating sequence p(v 0 , v n ) = (v 0 , e 1 , ..., e n , v n ), where n ≥ 1, and v 0 , ..., v n ∈ V , e 1 , ..., e n ∈ E, and |p(v 0 , v n )| = n that is the length of the path. For p(v 0 , v n ), v 0 is the source vertex and v n is the target vertex. If there exists a path from v 0 to v n , then v 0 reaches v n , denoted as v 0 ⇝ v n . The label sequence of the path p(v 0 , v n ) is Λ(p(v 0 , v n )) = (λ(e 1 ), ..., λ(e n )). When the context is clear, we also use Λ(u, v) to denote the sequence of edge labels of a path from u to v.

A. Minimum Repeats

We use l i to denote an edge label, L = (l 1 , ..., l n ) a label sequence, |L| = n the length of L, and ϵ the empty label sequence, i.e., |ϵ| = 0. We use • to denote the concatenation of label sequences (or labels), i.e., (l 1 , ..., l i ) • (l i+1 , ..., l n ) = (l 1 , ..., l n ), or L • L = L 2 . For the empty label sequence ϵ, we define

L • ϵ = ϵ • L = L.
The sequence

L ′ = (l ′ 1 , ..., l ′ n ′ ), |L ′ | = n ′ is a repeat of L = (l 1 , ..., l n ), if
there exists an integer z, such that n n ′ = z ≥ 1, and l ′ j = l j+i×n ′ for every j ∈ (1, ..., n ′ ) and i ∈ (0, ..., z -1). A repeat L ′ of L is minimum if L ′ has the shortest length of all the repeats of L. The minimum repeat (MR) of L is denoted as M R(L), which is also a sequence of edge labels. For example, given the path p = (P 10 , knows, P 11 , worksFor, P 12 , knows, P 13 , worksFor, P 16 ) in Fig. 1, we have M R(p(P 10 , P 16 )) =(knows, worksFor). If L = M R(L), we also say L itself is a minimum repeat. Given a positive integer k and a label sequence L, if |M R(L)| ≤ k, then we say L has a non-empty k-MR that is M R(L).

Lemma 1: For a label sequence L, M R(L) is unique. Suppose L has two minimum repeats, then only the shorter is M R(L). Therefore, we have Lemma 1.

B. RLC Query

We consider the path constraint L + = (l 1 , ..., l k ) + , where '+' is the Kleene plus, i.e., one-or-more concatenations of the sequence L = (l 1 , ..., l k ). A label sequence Λ(u, v) of a path p(u, v) satisfies a label-constraint L + , if and only if M R(Λ(u, v)) = L. If such a path p(u, v) exists, then u can reach v with the constraint L + , denoted as u

L + ⇝ v, otherwise u L + ̸ ⇝ v.
Notice that reachability queries with pathconstraints based on recursive concatenations could ask for additional constraints related to path length. For instance, if the path constraint is L + = (knows, knows) + , then the query would need to additionally check whether the path length is even. In general, such fragments of queries, i.e., queries with

L + s.t. L ̸ = M R(L)
, impose an additional constraint on path length leading to the complicated even-path problem (NPcomplete [START_REF] Mendelzon | Finding regular simple paths in graph databases[END_REF], [START_REF] Bagan | A trichotomy for regular simple path queries on graphs[END_REF], [START_REF] Lapaugh | The even-path problem for graphs and digraphs[END_REF] for simple paths), which is beyond the scope of our paper.

Definition 1 (RLC Query): Given an edge-labeled directed graph G = (V, E, L) and a recursive k, an RLC query is a triple (s, t, L + ), L = (l 1 , ..., l j ), where s, t ∈ V , L = M R(L), j ≤ k, and l i ∈ L for i ∈ (1, ..., j). If s L + ⇝ t, then the answer to the query is true. Otherwise, the answer is false.

For the sake of simplicity in this paper we focus on the RLC queries with the Kleene plus. Queries (s, t, L * ) with the Kleene star can be trivially reduced to queries with the Kleene plus (s, t, L + ) through checking whether s is equal to t. Our method is thus applicable to RLC queries with the Kleene star.

Given an RLC query Q(s, t, L + ), under the arbitrary path semantics, two naive approaches can be used to evaluate Q. As RLC queries are path queries with regular expressions, in the first approach, RLC queries can be evaluated by online graph traversals, e.g., BFS, guided by a minimized NFA (nondeterministic finite automaton) [START_REF] Bonifati | Querying Graphs[END_REF] that is constructed according to the regular expression in an RLC query. The second approach leads to pre-computing the transitive closure, which for each pair of vertices (s, t) records whether s ⇝ t and all the label sequences from s to t. Notice that the naive approach to build the transitive closure is not usable in our case because cycles may exist on the path from s to t such that the BFS from s can generate infinite label sequences for paths to t.

To address this issue, we adopt an extended transitive closure, which is presented in Section VI. As demonstrated in our experiments, these two solutions require either too much query time or storage space and are impractical for large graphs.

C. Indexing Problem

Our goal is to build an index to efficiently process RLC queries. The indexing problem is summarized as follows.

Problem 3.1: Given an edge-labeled graph G, the indexing problem is to build a reachability index for processing RLC queries on G, such that the size of the index is minimal and the correctness of query processing is preserved.

We observe that recording MRs, instead of raw label sequences of paths in G, can reduce the storage space, and such a strategy does not violate the correctness of query processing. The main benefits are twofold: (1) MRs are not longer than raw label sequences; (2) different raw label sequences may have the same MR. For example, in Fig. 1, there exist two paths from P 10 to P 16 having the label sequence (knows, knows, knows, knows) and (knows, knows, knows), which have the same MR knows.

Definition 2 (Concise Label Sequences): Let P(s, t) be the set of all paths from s to t. The concise set of label sequences from vertex s to t, denoted as S k (s, t), is the set of k-MRs of all label sequences from s to t, i.e., S k (s, t) = {L|p ∈ P(s, t), L = M R(Λ(p)), |L| ≤ k}.

To index RLC queries, we need to compute and record the concise label sequences. We have Proposition 1 by definition.

Proposition 1: s L + ⇝ t, |L| ≤ k in G iff L ∈ S k (s, t).
For example, in Fig. 1, we have S 2 (P 12 , P 16 ) = {(knows), (knows, worksFor)}. With S 2 (P 12 , P 16 ), RLC queries from P 12 to P 16 can be processed correctly.

IV. KERNEL-BASED SEARCH

In this section, we deal with the following question: how to compute concise label sequences? The problem for computing a concise label sequence is that if a cycle exists on a path from s to t, there exist infinite paths from s to t, which makes the computation of S k (s, t) infeasible, e.g., |P(P 11 , P 13 )| in Fig. 1 is infinite. We overcome this issue by leveraging the upper bound of recursively concatenated labels in a constraint, i.e., recursive k. We observed that we don't have to compute all possible label sequences for paths going from P 11 to P 13

Notation

Description p, or p(u, v) a path, or the path from u to v • the concatenation of labels or label sequences Λ(u, v), or Λ(p(u, v)) the label sequence of a path from u to v L a label sequence

L + a label constraint M R(L)
the minimum repeat of a label sequence L k the upper bound of the number of labels in

L + S k (u, v)
the concise set of minimum repeats from u to v u

L + ⇝ v, or u L + ̸ ⇝ v u reaches v through an L + -path, or otherwise u ⇝ v, or u ̸ ⇝ v u reaches v, or otherwise in(v), or out(v)
the set of vertices that can reach v, or v can reach aid(v)

the access id of vertex v by the indexing algorithm v (j) i a vertex with vertex id i and access id j as the set of label sequences L such that |M R(L)| ≤ k is actually finite. In general, let v be an intermediate vertex that a forward breadth-first search from s is visiting. The main idea is that when the path from s to v reaches a specific length, we can decide whether we need to further explore the outgoing neighbours of v. Moreover, if the outgoing neighbours of v are worth exploring, the following search can be guided by a specific label constraint. In the following, we first provide an illustrating example, and then formally define the specific constraint that is used to guide the subsequent search.

Example 2 (Illustrating Example): Consider the graph in Fig. 1. Assume we need to compute S 2 (P 11 , P 13 ), i.e., k = 2, and we perform a breadth-first search from P 11 . When P 13 is visited for the first time, we add (knows) and (worksFor, knows) into S 2 (P 11 , P 13 ). After that, when the search depth reaches 2k = 4, i.e., P 12 is visited for the second time, we can have 4 different label sequences, which are L 1 = (knows, knows, knows, knows), L 2 = (knows, knows, knows, worksFor), L 3 = (worksFor, knows, knows, knows), and L 4 = (worksFor, knows, knows, worksFor). Given this, all the 4 label sequences except L 1 do not need to be expanded anymore, because their expansions cannot produce a minimum repeat whose length is not larger than 2. After this, the following search continued with L 1 is guided by (knows) + that is computed from L 1 . However, because there already exists (knows) in S 2 (P 11 , P 13 ), the search terminates.

Definition 3: If a label sequence L can be represented as

L = (L ′ ) h • L ′′ , where h ≥ 2, L ′ ̸ = ϵ and M R(L ′ ) = L ′ ,
and L ′′ is ϵ or a proper prefix of L ′ , then L has the kernel L ′ and the tail L ′′ .

For example, the label sequence (knows, knows, knows, knows) from P 11 has a kernel knows and a tail ϵ.

Kernel-based search. When a kernel has been determined at a vertex that is being visited, the subsequent search to compute S k (s, t) can be guided by the Kleene plus of the kernel, e.g., (knows) + is used to guide the search in Example 2. We call this approach KBS (kernel-based search) in the remainder of this paper. In a nutshell, KBS consists of two phases: (1) kernel-search and (2) kernel-BFS, where the first phase is to compute kernels, and the second to perform kernel-guided BFS. We show in Theorem 1 that KBS can compute a sound and complete S k (s, t).

Theorem 1: Given a path p from u to v and a positive integer k, p has a non-empty k-MR if and only if one of the following conditions is satisfied, -Case 1:

|p| ≤ k. M R(Λ(p)) is the k-MR of p; -Case 2: k < |p| ≤ 2k. If |M R(Λ(p))| ≤ k, M R(Λ(p)) is the k-MR of p; -Case 3: |p| > 2k. Let x be the intermediate vertex on p, s.t. |p(u, x)| = 2k. If Λ(p(u, x)) has a kernel L ′ and a tail L ′′ , and M R(L ′′ • Λ(p(x, v))) = L ′ , then L ′ is the k-MR of p.
The proof of Theorem 1 is included in our technical report [START_REF] Zhang | A reachability index for recursive label-concatenated graph queries[END_REF] due to the space limit.

We discuss below two strategies to compute kernels based on Theorem 1, namely lazy KBS and eager KBS, and explain why eager KBS is better than lazy KBS, which is used in our indexing algorithm presented in Section V-B.

Lazy KBS. Theorem 1 can be transformed into an algorithm to find kernels, i.e., for a source vertex we generate all paths of length 2k, and then compute all the kernels of these paths. This strategy is referred to as lazy KBS, which means kernels are correctly determined when the length of paths reaches 2k, e.g., lazy KBS is used in Example 2.

Eager KBS. In contrast to the lazy strategy, we can determine kernel candidates earlier, instead of valid kernels that require the length of paths to be 2k. The main idea is to treat any k-MR that is computed using any path p, |p| ≤ k as a kernel candidate which is then used to guide KBS. Although an invalid kernel may be included, the search guided by the invalid kernel will not reach a target vertex through a path of which the k-MR is the invalid kernel. Thus, the result computed by the eager strategy is still sound and complete.

Example 3: Consider the example of computing S 2 (P 10 , P 13 ) in Fig. 1. Using the eager strategy, when P 12 is visited for the first time, two kernel candidates can be determined, i.e., (knows) and (knows, worksFor). Although (knows, worksFor) + is an invalid kernel, the search guided by it cannot reach P 13 .

The key advantage of the eager strategy over the lazy strategy is that it allows us to advance KBS from the kernelsearch phase to the kernel-BFS phase. This can make KBS more efficient because generating all label sequences of length 2k from a source vertex is more expensive than the case of paths of length k, especially on a dense graph.

V. RLC INDEX

In this section, we present the RLC index, and the corresponding query and indexing algorithm.

A. Overarching Idea

Given an RLC query (s, t, L + ), |L| ≤ k, the idea is to check whether there exists a path (s, ..., u, ..., t) whose label sequence satisfies the label constraint L + , where u is an intermediate vertex in p. In other words, the query is answered by concatenating two MRs of the sub-paths of p, i.e., M R(Λ(s, u)) and M R(Λ(u, t)).

(1) 1 v (3) 2 v (2) 3 v (4) 4 v (5) 5 v (6) 6 l 1 l 1 l 1 l 2 l 1 l 2 l 3 l 1 l 1 l 2 l 2
Fig. 2. A graph instance G for illustrating the RLC index.

Definition 4 (RLC Index): Let G = (V, E, L) be an edgelabeled graph and recursive k be a positive integer. The RLC index of G assigns to each vertex v ∈ V two sets:

L in (v) = {(u, L ′ )|u ⇝ v, L ′ ∈ S k (u, v))}, and L out (v) = {(w, L ′′ )|v ⇝ w, L ′′ ∈ S k (v, w)}.
Therefore, there is a path p(s, t) satisfying an arbitrary constraint L + , |L| ≤ k, if and only if one of the following cases is satisfied,

• Case 1: ∃(x, L ′ ) ∈ L out (s) and ∃(x, L ′′ ) ∈ L in (t), such that L ′ = L ′′ = L; • Case 2: ∃(t, L ′′′ ) ∈ L out (s) or ∃(s, L ′′′ ) ∈ L in (t), such that L ′′′ = L.
Example 4 (Running Example of the RLC Index): Consider the graph G shown in Fig. 2. The RLC index with recursive k = 2 for G is presented in Table II

. We have Q 1 (v 3 , v 6 , (l 2 , l 1 ) + ) = true because ∃(v 1 , (l 2 , l 1 )) ∈ L out (v 3 ) and ∃(v 1 , (l 2 , l 1 )) ∈ L in (v 6 ). Indeed, there exists the path (v 3 , l 2 , v 4 , l 1 , v 1 , l 2 , v 3 , l 1 , v 6 ) from v 3 to v 6 in the graph in Fig. 2. For Q 2 (v 1 , v 2 , (l 2 , l 1 ) + ), the answer is true because ∃(v 1 , (l 2 , l 1 )) ∈ L in (v 2 ). Given Q 3 (v 1 , v 3 , (l 1 ) + ), the answer is f alse. Although v 1 can reach v 3 , e.g., ∃(v 1 , l 2 ) ∈ L in (v 3 ), the constraint (l 1 ) + of Q 3 cannot be satisfied.
Whereas our indexing framework leverages the canonical 2-hop labeling framework for plain reachability queries [START_REF] Cohen | Reachability and distance queries via 2-hop labels[END_REF], indexing RLC queries is inherently more challenging due to the presence of complex recursive label concatenations, which calls for the design of a novel indexing algorithm.

In order to save storage space, when building an RLC index, redundant index entries have to be removed as many as possible, i.e., building a minimal (or condensed) RLC index. The underlying idea is that if there exists a path p such that u L + ⇝ v, then the RLC index only records the reachability information of the path p once, i.e., either through Case 1 or Case 2 in Definition 4. This leads to the following definition.

Definition 5 (Condensed RLC Index):

The RLC index is condensed, if for every index entry (s, L) ∈ L in (t) (or (t, L) ∈ L out (s)), there do not exist index entries (u, L ′ ) ∈ L out (s) and (u, L ′′ ) ∈ L in (t) such that L = L ′ = L ′′ .
We focus on designing an indexing algorithm that can build a correct (sound and complete) and condensed RLC index.

B. Query and Indexing Algorithm

The query algorithm is presented in Algorithm 1, where we use I to denote an index entry. Each index entry I has the schema (vid, mr), where vid represents vertex id and mr the recorded minimal repeat. Given an RLC query (s, t, L + ), to efficiently find (u, L ′ ) ∈ L out (s) and (u, L ′′ ) ∈ L in (t), we execute a merge join over L out (s) and L in (t), shown at line 4 in Algorithm 1. The output of the merge join is a set of index entry pairs (I ′ , I ′′ ), s.t. I ′ .vid = I ′′ .vid. Case 1 of the

FIG. 2. V L in (v) L out (v) v 1 - (v 1 , l 2 ), (v 1 , l 1 ), (v 1 , (l 2 , l 1 )) v 2 (v 1 , l 1 ), (v 1 , (l 2 , l 1 )) (v 1 , (l 2 , l 1 )), (v 1 , l 1 ) v 3 (v 1 , l 2 ), (v 1 , (l 1 , l 2 )) (v 1 , l 2 ), (v 1 , (l 2 , l 1 )), (v 1 , l 1 ), (v 3 , (l 1 , l 2 )) v 4 (v 1 , l 2 ) (v 1 , l 1 ), (v 3 , (l 1 , l 2 )) v 5 (v 1 , (l 1 , l 2 )), (v 1 , l 1 ),(v 3 , (l 1 , l 2 )), (v 2 , l 2 ) (v 1 , l 1 ), (v 3 , (l 1 , l 2 )) v 6 (v 1 , (l 2 , l 1
)), (v 3 , l 1 ), (v 3 , (l 2 , l 3 )), (v 4 , l 3 ) -RLC index (see Definition 4) is checked at line 5. Case 2 is checked at line 3. If one of these cases can be satisfied, the answer true will be returned immediately. Otherwise, index entries in L out (s) and L in (t) are exhaustively merged, and the answer false will be returned at last. In the remainder of this subsection, we present an indexing algorithm (Algorithm 2) to build the RLC index that is sound, complete and condensed. We use v i to denote a vertex with id i. Given a graph G(V, E, L), the indexing algorithm mainly performs backward and forward KBS from each vertex in V to create index entries, and pruning rules are applied to accelerate index building as well as remove redundant index entries.

Indexing using KBS. We explain below how the backward KBS creates L out -entries. The forward KBS follows the same procedure, except that L in -entries will be created. Suppose that the backward KBS from vertex

v i is visiting v. If |M R(Λ(v, v i ))| ≤ k, then we add (v i , M R(Λ(v, v i ))) into L out (v).
Although there may be cycles in a graph, the KBS will not go on forever, because when the depth of the search reaches k, the KBS will be transformed from its kernel-search phase into its kernel-BFS phase that is then guided by the Kleene plus of a kernel candidate, such that the KBS can terminate if any invalid label (or state) transition is met, or a vertex being visited with a label l i of the kernel has been already visited with a label l j of the kernel, s.t. i = j.

KBSs are executed from each vertex in V and the execution follows a specific order. The idea is to start with vertices that have more connections to others, allowing such vertices to be intermediate hops to remove redundancy. In the RLC index, we leverage the IN-OUT strategy, i.e., sorting vertices according to (|out(v)| + 1) × (|in(v)| + 1) in descending order, which is known as an efficient and effective strategy for various reachability indexes based on the 2-hop labeling framework. The id of vertex v in the sorted list is referred to as the access id of v, denoted as aid(v) starting from 1, e.g., for the graph in Fig. 2, the sorted list is

(v 1 , v 3 , v 2 , v 4 , v 5 , v 6 ), where aid(v 3 ) = 2, or simply v (2) 3
in Fig. 2. Example 5 (Running Example of Indexing): Consider the graph in Fig. 2 and the RLC index in Table II with recursive k = 2. The KBSs are executed from each vertex in the order of (v 1 , v 3 , v 2 , v 4 , v 5 , v 6 ). We explain below the backward KBS from v 1 , which is the first search of the indexing algorithm. The traversal of depth 1 of this backward KBS visits v 4 and creates (v 1 , l 1 ) in L out (v 4 ), visits v 3 and creates (v 1 , l 2 ) in L out (v 3 ), and visits v 5 and creates (v 1 , l 1 ) ∈ L out (v 5 ). The Algorithm 1: Query Algorithm.

1 procedure Query(s, t, L + ) 2 if ∃(t, L) ∈ Lout(s) or ∃(s, L) ∈ L in (t) then
traversal of depth 2 creates (v 1 , (l 2 , l 1 )) in L out (v 3 ), (v 1 , l 2 ) in L out (v 1 ), (v 1 , l 1 ) ∈ L out (v 2 ), and (v 1 , (l 2 , l 1 )) ∈ L out (v 2 ).
Then, the kernel-search phase of this KBS terminates as the depth of the search reaches 2, which generates kernel candidate l 1 with a set of frontier vertices {v 4 , v 5 , v 2 }, kernel candidate l 2 with a set of frontier vertices {v 3 , v 1 }, and kernel candidate (l 2 , l 1 ) with a set of frontier vertices (v 3 , v 2 ). After this, this KBS is turned into three kernel-BFSs guided by (l 1 ) + , (l 2 ) + , and (l 2 , l 1 ) + with the corresponding frontier vertices. The kernel-BFS terminates under the case of an invalid label transition or a repeated visiting. For example, the label of the incoming edge of v 3 is l 2 , which is an invalid state transition of (l 2 , l 1 ) + in the backward kernel-BFS from v 1 , such that the kernel-BFS guided by (l 2 , l 1 ) + terminates at v 3 . For another example, index entry (v 1 , l 1 ) ∈ L out (v 1 ) is created when v 1 is visited for the first time by the kernel-BFS from v 1 guided by (l 1 ) + , but this kernel-BFS will not continue when it visits v 5 that has already been visited with the label l 1 .

Pruning Rules. To speed up index construction and remove redundant index entries, we apply pruning rules during KBSs. For ease of presentation, we present the rules for backward KBSs, and the same rules apply for forward ones. -PR1: If the k-MR of an index entry that needs to be recorded can be acquired from the current snapshot of the RLC index, then the index entry can be skipped. -PR2: If vertex v i is visited by the backward KBS performed from vertex v i ′ s.t. aid(v i ′ ) > aid(v i ), then the corresponding index entry can be skipped. -PR3: If vertex v i is visited by the kernel-BFS phase of a backward KBS performed from vertex v i ′ , and PR1 (or PR2) is triggered, then vertex v i and all the vertices in in(v i ) are skipped. The correctness of Algorithm 2 with pruning rules is guaranteed by Theorem 3 presented in Section V-C.

Example 6 (Running Example of Pruning Rules): Consider the forward KBS from v 3 for the graph in Fig. 2. It can visit v 2 through label sequence (l 2 , l 1 ), such that it tries to create (v 3 , (l 2 , l 1 )) in L in (v 2 ). However, there already exist (v 1 , (l 2 , l 1 )) ∈ L out (v 3 ) and (v 1 , (l 2 , l 1 )) ∈ L in (v 2 ), such that Q(v 3 , v 2 , (l 2 , l 1 ) + ) = true with the current snapshot of the RLC index, i.e., the reachability information has already been recorded. Thus, the index entry (v 3 , (l 2 , l 1 )) in L in (v 2 ) is pruned according to PR1. As an example of PR2, consider the backward KBS from v 2 . It can visit v 1 through path (v 1 , l 2 , v 3 , l 1 , v 2 ), such that it tries to create (v 2 , (l 2 , l 1 )) in L out (v 1 ). Given aid(v 2 ) > aid(v 1 ), the index entry can be pruned by PR2. Consider the forward KBS Algorithm 2: Indexing Algorithm. q ← an empty queue of (vertex, label sequence); 8 q.enqueue(v, ϵ); 9 map ← a map of (kernel candidates, vertex set); 10 while q is not empty do 11 (x, seq) ← q.dequeue(); q ← an empty queue of (vertex, integer); 27 for x ∈ vSet do 28 mark x as visited by state 1, q.enqueue(x, |L|); 29 while q is not empty do 30 (x, i) ← q.dequeue(), i ← i -1; from v 2 for an example of PR3. It visits v 2 through path (v 2 , l 2 , v 5 , l 1 , v 1 , l 2 , v 3 , l 1 , v 2 ), where at the edge (v 5 , l 1 , v 1 ) the KBS is transformed from the kernel-search phase to the kernel-BFS phase that is then guided by (l 2 , l 1 ) + . When v 2 visits itself for the first time, the KBS tries to create index entry (v 2 , (l 2 , l 1 )) ∈ L in (v 2 ). However, this index entry can be pruned by PR1 because of (v 1 , (l 2 , l 1 )) ∈ L out (v 2 ) and (v 1 , (l 2 , l 1 )) ∈ (v 2 ). Then, PR3 is triggered, which means the kernel-BFS from v 2 with the kernel (l 2 , l 1 ) + can terminate.

31 if i = 0 then i = |L| ; 32 label l ← L.get(i);
The indexing algorithm is presented in Algorithm 2. For ease of presentation, each procedure focuses on the backward case, and the forward case can be obtained by trivial modifications, e.g., replacing incoming edges with outgoing edges. We use the KMP algorithm [START_REF] Knuth | Fast pattern matching in strings[END_REF] to compute the minimum repeat of a label sequence, i.e., MR() at line 13 in Algorithm 2. The indexing algorithm performs backward and forward KBS from each vertex. The KBS from a vertex v consists of two phases: kernel-search (line 6 to line 18) and kernel-BFS (line 25 to line 38). The kernel-search returns for each vertex v all kernel candidates and a set of frontier vertices vSet. The kernel-BFS is performed for each kernel candidate, i.e., a BFS with vertices in vSet as frontier vertices guided by a kernel candidate. PR1 and PR2 are included at line 20, which can be triggered by both kernel-search and kernel-BFS. However, RP3 can only be triggered by kernel-BFS, which is implemented at line 36, i.e., if the insert function returns true, then vertices can be pruned during the search. However, PR3 is not related to kernel-search that focuses on generating kernels, such that the result returned by the insert function at line 14 is not taken into account.

C. Analysis of RLC Index

In Theorem 2, we present that pruning rules can guarantee the condensed property of the RLC index, and in Theorem 3, that the RLC index constructed by Algorithm 2 is correct, i.e., sound and complete.

Theorem 2: With pruning rules, the RLC index is condensed. Theorem 3: Given an edge-labeled graph G and the RLC index of G with a positive integer k built by Algorithm 2, there exists a path from vertex s to vertex t in G which satisfies a label constraint L + , |L| ≤ k, if and only if one of the following condition is satisfied

(1) ∃(x, L) ∈ L out (s) and ∃(x, L) ∈ L in (t); (2) ∃(t, L) ∈ L out (s), or ∃(s, L) ∈ L in (t).
The proofs of Theorem 2 and 3 are included in our technical report [START_REF] Zhang | A reachability index for recursive label-concatenated graph queries[END_REF] due to the space limit.

We analyze the complexity of the RLC index below. Query time. Given a query Q(s, t, L + ), the time complexity of Algorithm 1 is O(|L out (s)| + |L in (t)|), because we only need to take O(|L out (s)| + |L in (t)|) time to apply the merge join to find (x, L) ∈ L out (s) and (x, L) ∈ L in (t). Note that index entries in L out (s) and L in (t) have already been sorted according to the access id of vertices, such that we do not need to sort index entries when applying the merge join. Notice that these complexities resemble the complexity classes of previous label-constraint reachability indexes [START_REF] Valstar | Landmark indexing for evaluation of label-constrained reachability queries[END_REF], [START_REF] Peng | Answering billion-scale label-constrained reachability queries within microsecond[END_REF] for LCR queries.

VI. EXPERIMENTAL EVALUATION

In this section, we study the performance of the RLC index. We first used real-world graphs to evaluate the indexing time, index size, and query time of the RLC index, where we focused on practical graphs and workloads. Then, we used synthetic graphs to conduct a comprehensive study of the impact of different characteristics on the RLC index, including label set size, average degree, and the number of vertices. Finally, we compared the query time of the RLC index with existing systems, where we considered more types of reachability queries from real-world query logs in order to demonstrate the generality of our approach.

a) Baselines: To the best of our knowledge, the RLC index is the first indexing technique designed for processing recursive label-concatenated reachability queries, and indices for other types of reachability queries are not usable in our context because of specific path constraints defined in the RLC queries. Thus, the chosen baselines for the RLC index are online graph traversals guided by NFAs (see Section III-B). We consider both BFS (breadth-first search) and BiBFS (bidirectional BFS) as the underlying online traversal methods, and simply refer to the baselines as BFS and BiBFS in this section. We note that DFS (depth-first search) is an alternative to BFS with the same time complexity but is not as efficient as BiBFS. In addition, we also include an extended transitive closure as a baseline, referred to as ETC. The indexing algorithm of ETC performs a forward KBS from each vertex without pruning rules, and records for every reachable pair of vertices (u, v) any k-MR of any path p(u, v). In ETC, we use a hashmap to store reachable pairs of vertices and the corresponding set of k-MRs. There are two differences between the indexing algorithm of ETC and the one of the RLC index: (1) only forward KBS is used for building ETC, instead of forward and backward KBS for the RLC index, and (2) none of the pruning rules is applied for building ETC.

b) Datasets: We use real-world datasets and synthetic graphs in our experiments. We present the statistics of realworld datasets in Table III (sorted according to |E|), which are from either the SNAP [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF] or the KONECT [START_REF] Kunegis | Konect: The koblenz network collection[END_REF] project. We also include for each graph the loop count (cycles of length 1) and the triangle count (cycles of length 3) shown in the last two columns in Table III Execution Time (us) X X X X X X X X X X X X X X True-Queries AD EP TW WN WS WG WT WB WH PR SO LJ WF Graphs 10 3 10 4 10 5 10 6 10 7 10 8 10 9

Execution Time (us) X X X X X X X X X X X X X False-Queries for graphs that do not have labels on their edges, indicated by the column of synthetic labels in Table III. The edge labels have been generated according to the Zipfian distribution [START_REF] Bagan | gMark: Schema-driven generation of graphs and queries[END_REF] with exponent 2. The synthetic graphs used in our experiments follows two different modes, namely the Erdős-Rényi (ER) model and the Barabási-Albert (BA) model. We use JGraphT [START_REF] Michail | JGraphT-A java library for graph data structures and algorithms[END_REF] to generate the ER-and BA-graphs. The main difference between ER-graphs and BA-graphs is that ER-graphs have an almost uniform degree-distribution while BA-graphs have a skew in it because BA-graphs contain complete sub-graphs. The method to assign labels to edges in synthetic graphs is the same as the one used for real-world graphs.

c) Query generation: As a common practice to evaluate a reachability index in the literature, e.g., [START_REF] Valstar | Landmark indexing for evaluation of label-constrained reachability queries[END_REF]- [START_REF] Chen | Graph indexing for efficient evaluation of label-constrained reachability queries[END_REF], we generate for each real-word graph comprehensive query sets, each of which contains 1000 true-queries and 1000 false-queries, respectively. We explain the method for query generation as follows. We uniformly select a source vertex s and a target vertex t, and also uniformly choose a label constraint L + . Then, a bidirectional breadth-first search is conducted to test whether s reaches t under the constraint of L + . If the test returns true, we add (s, t, L + , true) to the true-query set, otherwise we add it into the false-query set. After that, we generate another (s, t, L + ), and repeat the above procedure until the completion of the two query sets.

d) Implementation and Setting: Our open-source implementation has been done in Java 11, spanning baseline solutions and the RLC index. We run experiments on a machine with 8 virtual CPUs of 2.40GHz, and 128GB main memory, where the heap size of JVM is configured to be 120GB.

A. Performance on Real-World Graphs

In this section, we analyze the performance of the RLC index on real-world graphs. We first compare the RLC index with ETC in terms of indexing time and index size, and with BFS and BiBFS in terms of query time. The recursive k value is set to 2, and each query in the respective workload has a recursive concatenation of 2 labels. The goal of the first experiment is to understand the performance of the RLC index for practical RLC query workloads whose length of recursive concatenation is at most 2, as in practical property paths [START_REF] Bonifati | Navigating the maze of wikidata query logs[END_REF]. After that, we conduct experiments on real-world graphs with different recursive k values to understand the impact for general queries.

Indexing time. Table IV shows the indexing time of the RLC index and ETC on real-world graphs, where "-" indicates that the method timed out on the graph. Building ETC cannot be completed in 24 hours for real-world graphs (or it runs out of memory) except for the AD graph with the lowest number of edges. The RLC index for the AD graph can be built in 0.7s, leading to a four-orders-of-magnitude improvement over ETC. The indexing time improvement of the RLC index over ETC is mainly due to the pruning rules that skip vertices in graph traversals when building the RLC index. Thus, this experiment also shows the significant impact of pruning rules in terms of indexing time. The indexing time of the RLC index for the first 10 graphs is at most 1 hour. The last three graphs, i.e., the SO graph, the LJ graph, and the WF graph are more challenging than the others, not only because they have more vertices and edges, but also because they have a larger number of loops and triangles, as shown in Table III. The SO graph has the longest indexing time due to its highly dense and cyclic character, i.e., it has 15M loops and 114M triangles. Although the WF graph has much fewer loops than the SO graph, it contains 30B triangles. Consequently, the indexing time of the WF graph is at the same order of magnitude as the one of the SO graph.

While it has more vertices, triangles, and edge labels than the SO graph, the LJ graph requires a lower indexing time.

Index size. Table IV shows the size of the RLC index for real-world graphs. The size of the RLC index is much smaller than the size of ETC for the AD graph (that is the only graph ETC can be built within 24 hours). The index size improvement is because of not only the indexing schema of the RLC index but also the application of pruning rules that can avoid recording redundant index entries. The effectiveness of pruning rules can also be observed between the PR graph and the SO graph. Although the SO graph is larger than the PR graph in terms of the number of vertices and the number of edges, the index size of the SO graph is smaller than the index size of the PR graph. Thus, this experiment also demonstrates the significant impact of pruning rules in terms of index size. Query time. Fig. 3 shows the execution time of the truequery set and the false-query set. In general, the execution time of a query set of 1000 queries using the RLC index is around 1 millisecond for all the graphs in Table III, except for the WF graph (that has the largest number of edges) for which it is around 2 milliseconds. Query execution using BFS times out for the true-queries on both the SO graph and the WF graph, and for the false queries on the WF graph. In addition, we only report the query time of ETC for the AD graph as ETC cannot be built for all the other graphs. As shown in Fig. 3, the RLC index shows an up to sixorders-of-magnitude improvement over BFS and four-ordersof-magnitude improvement over BiBFS. The query time using the RLC index is slightly faster than ETC, because the larger number of reachable pairs of vertices recorded in ETC leads to a slight overhead of checking for the reachability between a source s and a target t and also the existence of a minimum repeat of a path from s to t.

Different recursive k values. We analyze the impact of the recursive k values on real-world graphs. For space reasons, we have focused on the TW and WG datasets, i.e., graphs from Twitter and Google. The indexing results are shown in Figure 4, where we also report the query time of 1000 true-queries and 1000 false-queries with a recursive concatenation of 2, 3, and 4 labels. As expected, the indexing time and index size of the RLC index increase when the recursive k value increases, and the larger index size with more path constraints can also lead to the increase of query time. The main reason is that the number of path-constraints (kernels) will exponentially grow as the increase of k, and the kernel-search phase of the indexing algorithm needs to take into consideration the potential path-constraints that exist in the graph. Notice that the increase rate of the index size is much slower than the increase rate of the indexing time, which means that the number of paths that can satisfy path constraints of recursive concatenations is not increasing as the increase of the length of the constraints, i.e., the recursive k value. The main reason is that in real-world graphs only only a few labels have a large number of occurrences (Zipfian distribution) as shown in existing benchmarks e.g., gMark [START_REF] Bagan | gMark: Schema-driven generation of graphs and queries[END_REF]. Consequently, a long concatenation of edge labels cannot repeat frequently due to the lack of desired labels. Thus, RLC queries with a large recursive k value may not need indexing.

Summary and outlook. Our indexing algorithm designed for an arbitrary recursive k value can efficiently build the RLC index for processing practical RLC queries that are difficult to evaluate in modern graph query engines. Specifically, the recursive concatenation length of RLC queries in recent opensource query logs [START_REF] Bonifati | Navigating the maze of wikidata query logs[END_REF] is not larger than 2 and such practical RLC queries appear quite often in time-out logs. As shown in Table IV and Fig. 3, the RLC index with a recursive k of 2 can be efficiently built even for large and highly dense real-world graphs, and can significantly improve the processing time of such timed out queries in practice.

B. Impact of Graph Characteristics

In this section, we focus on analyzing the performance of the RLC index on synthetic graphs (ER-graphs and BA-graphs) with different characteristics, namely average degree, label set size, and the number of vertices. The recursive k value is set to 2 in this section, and more experiments about different k values on synthetic graphs are presented in our technical report [START_REF] Zhang | A reachability index for recursive label-concatenated graph queries[END_REF]. For each graph, we generate a query set of 1000 true-queries and a query set of 1000 false-queries, which are referred to as ER.T and ER.F for an ER-graph, and BA.T and BA.F for a BA-graph.

1) Impact of label set size and average degree: In this experiment, we use BA-graphs and ER-graphs with 1M vertices, and we vary the average degree d in [START_REF] Sahu | The ubiquity of large graphs and surprising challenges of graph processing[END_REF][START_REF] Agrawal | Efficient management of transitive relationships in large data and knowledge bases[END_REF][START_REF] Jagadish | A compression technique to materialize transitive closure[END_REF][START_REF] Cohen | Reachability and distance queries via 2-hop labels[END_REF], and label set size |L| in [START_REF] Jin | Efficiently answering reachability queries on very large directed graphs[END_REF][START_REF] Chen | Stack-based algorithms for pattern matching on dags[END_REF][START_REF] Veloso | Reachability queries in very large graphs: A fast refined online search approach[END_REF][START_REF] Cai | Path-Hop: Efficiently indexing large graphs for reachability queries[END_REF][START_REF] Valstar | Landmark indexing for evaluation of label-constrained reachability queries[END_REF][START_REF]Neo4j[END_REF][START_REF] Bebee | Amazon Neptune: Graph data management in the cloud[END_REF][START_REF]Virtuoso[END_REF], e.g., a graph with d = 5 and |L| = 16 has 1M vertices, 5M edges, and 16 distinct edge labels. We aim at analyzing indexing time, index size, and query time of the RLC index when d and |L| increase. The experimental results for ER-graphs and BA-graphs are reported in Fig. 5. We discuss the results below.

Indexing time. We observe in Fig. 5 that the indexing time for the used ER-graphs and BA-graphs with a fixed d shows a linear increase (for most cases) as |L| increases. This can be understood as follows. When |L| increases, the number of possible minimum repeats increases, requiring more time for the kernel-search phase of a KBS in the indexing algorithm to traverse the graph and generate potential kernel candidates, resulting in more kernel-BFS executions. The total number of possible minimum repeats can be quadratic in |L| in the worst case when the input parameter k of the RLC index is two. Furthermore, because there are more edges to traverse, the indexing time for both ER-graphs and BA-graphs with a fixed |L| increases linearly as d increases.

Index size. As illustrated in Fig. 5, an increase in average degree d can result in a larger index size for both ER-graphs and BA-graphs. The reason is that a vertex s can reach a vertex t through more paths, leading to a higher number of minimum repeats being recorded. As the size of the label set grows, the corresponding impact on ER-graphs is different from the one on BA-graphs. Specifically, the increase is negligible for ERgraphs with a small d, e.g., 2, and becomes more noticeable for ER-graphs with a large d, e.g., 5. For any d, however, we see a clear linear increase in index size with the growth in |L| for BA-graphs. This is because a BA-graph comprises a complete sub-graph, and vertices inside the complete subgraph have higher degrees. Therefore, the KBSs executed from such vertices can create more index entries as |L| grows, as d=2 d=3 d=4 d=5 it can reach other vertices through paths with more distinct minimum repeats. However, because of the uniform degree distribution, the increase in the number of minimum repeats of paths from a vertex s to a vertex t due to an increase in |L| is not significant for ER-graphs when d is small, but the corresponding impact becomes stronger when d is larger. Query time. As shown in Fig. 5 the growth of |L| has a different impact on query time. More precisely, when |L| rises, the execution time of both true-and false-queries for ERgraphs remains steady. When it comes to BA-graphs, increasing |L| can lead to a minor boost in true-query execution time but has almost no impact on false-query execution time. This is due to the fact that the vertices in the complete sub-graph of a BA-graph can reach much more vertices than the vertices outside the complete sub-graph in the BA-graph, leading to a skew in the distribution of vertices in index entries, i.e., many index entries have the same vertex. Furthermore, when |L| grows, the number of minimum repeats also increases, which makes the skew higher. As a result, processing true-queries will encounter situations where the query algorithm searches for a particular minimum repeat in a significant number of index entries with the same vertex. However, for false-queries, the query result can be returned instantly if there are no index entries with the same vertex. Fig. 5 also shows that d has a negligible impact on the execution time of the true-queries on the BA graph. The main reason is that the number of index entries for some vertices in the BA graph does not increase significantly w.r.t the increase of d because of the skew in the degree distribution and a fixed |L|.

2) Scalability: In this experiment, we use BA-graphs and ER-graphs with average degree 5, 16 edge labels, and vary the number of vertices in (125K, 250K, 500K, 1M, 2M). The goal is to analyze the scalability of the RLC index in terms of |V |. The results of indexing time, index size, and query time for both ER-graphs and BA-graphs are reported in Fig. 6.

Indexing time and index size. Fig. 6 shows that indexing time and index size grows with the increase of the number of vertices. The main reason is that graphs with more vertices require more KBS iterations, which increases indexing time and also the number of index entries. We observe that indexing BA-graphs is more expensive than indexing ERgraphs because of the presence of a complete sub-graph in the former. We also observe that the different topological structures between BA-graphs and ER-graphs have different impacts on the increasing rate of index size w.r.t |V |. The uniform degree distribution in ER-graphs makes the index size increase with a sharper rate than the one of BA-graphs, because BA-graphs contain a significant number of vertices of high degree, which is also growing as |V | increases, and the indexing algorithm starts building the index from these vertices such that index entries containing these vertices can be leveraged to prune redundant index entries that need to be inserted later on.

Query time. Fig. 6 shows that query time on the ER-graphs and true-query time on the BA-graphs slightly increase as the number of vertices grows, as expected on larger graphs. In addition, the false-query time is higher than the true-query time on ER-graphs, and the true-query time is higher than the false-query time on BA-graphs. We interpret the results as follows. Given a query (s, t, L + ) on a graph which has a uniform distribution in vertex degree, the index entries (v, mr) in both L out (s) and L in (t) also have a uniform distribution in terms of v. Thus, the query algorithm (based on merge join) need to perform an exhaustive search in L out (s) and L in (t) to find index entries with the same vertex v, which results in false-queries taking longer time to execute than true-queries. However, when the distribution of vertex degree is skewed in BA-graphs, the index entries in L out (s) and L in (t) are dominated by vertices of high degree. In addition, as there are many paths passing through high-degree vertices with distinct minimum repeats, the number of index entries with such vertices is also large. Thus, the query algorithm can perform a faster search for false-queries than true-queries, because the number of distinct vertices in both L out (s) and L in (t) is not large. Notice that the number of vertices of high degree also increases as |V | increases. For false-queries in BA-graphs, the dominance of index entries with high-degree vertices becomes stronger as |V | increases. Consequently, the number of index entries in L out (s) and L in (t) with distinct vertex id can decrease, which makes the merge-join algorithm execute faster. The query algorithm, on the other hand, needs to select a specific mr among index entries with vertex u of a high degree to process true-queries, which takes more time.

C. Comparison with Existing Systems

In this section, we focus on evaluating how much improvement the RLC index can provide over mainstream graph processing systems. We recall that many current graph query engines fail to evaluate RLC queries, thus we focused on three systems that are able to evaluate these queries on property graphs and RDF graphs. In order to show how the index performs with varying types of queries, such as longer concatenations or path queries frequently occurring in realworld query logs, we consider the following queries: Q1 being a single label under the Kleene plus a + ; Q2 consisting of a concatenation of length 2 (a • b) + ; Q3 having the expression (a • b • c) + thus a concatenation of length 3. In this case, we build the index with k = 3 to support all the three RLC queries, especially Q3 having the longest concatenation. For the sake of completeness, an extended reachability query with the constraint a + • b + is also included in this experiment, referred to as Q4. We have employed Q4 to study the generality and applicability of the RLC index to a wide range of regular path queries in real-world graph query logs [START_REF] Bonifati | Navigating the maze of wikidata query logs[END_REF]. To deal with this query, we use the RLC index in combination with an online traversal to continuously check whether intermediately visited vertices can satisfy the path constraint.

Three graph engines used in the experiments, including commercial and open-sourced ones, have been selected as representatives of the few available graph engines capable of evaluating RLC queries. We do not reveal the identity of all the systems as some are proprietary and we cannot release performance data. Anonymized engines are referred to as Sys1 and Sys2 in the results, and the third one is Virtuoso Open-Source Edition (v7.2.6.3233). For the systems that support multi-threaded query evaluation, we set the system to singlethreaded to ensure a fair comparison with our approach, which is single-threaded only. For Virtuoso, we disabled the transaction logging to avoid additional overheads, and configured it to work entirely in memory by setting the maximum amount of memory for transitive queries to the available memory of the server. Note that these systems have their own indexes by default, for which we leave the configuration unchanged, e.g., Virtuoso 7 has column-wise indexes by default. These indexes are not suitable for RLC queries, as confirmed by our comparative analysis. We use the WN graph as a representative of real-world graphs, which has a moderate number of vertices and edges, along with a sufficient number of cycles to evaluate. We build one RLC index with the parameter k = 3 for the WN graph and use it to process all four queries. In this case, the RLC index of the WN graph can be built in 5.9 minutes and takes up 821 megabytes. We run each query using each system within the 10-minutes time limit, and we repeat the execution 20 times and report the median of the query execution time. We use two metrics to evaluate the improvement of the RLC index, namely (SU) and the workload size breakeven points (BEP). SU shows the query time improvement of the RLC index over an included graph system. BEP indicates the number of queries that make the indexing time of the RLC index pay off. Table V shows the results, where "-" indicates that the query execution of this system timed out. The RLC index shows that using a single index lookup can lead to significant speed-ups over included systems for processing Q3, which has the longest concatenation under the Kleene plus. We use the BEP value to understand the amortized cost of using the RLC index to accelerate Q3 processing. In particular, executing Q3 130 times on Sys2 is equivalent to the time it takes to build and query the RLC index the same number of times. The RLC index can also significantly improve the execution time for Q1, Q2, and Q4.

VII. CONCLUSION

In this paper, we introduced RLC queries, which are reachability queries with a path constraint based on the Kleene plus over a concatenation of edge labels. RLC queries are becoming relevant in real-world applications, such as social networks, financial transactions and SPARQL endpoints. In order to efficiently process RLC queries online, we propose the RLC index, the first reachability index that is suitable for these queries. We design an indexing algorithm with pruning rules to not only accelerate the index construction but also remove redundant index entries. Our comprehensive experimental study demonstrates that the RLC index allows to strike a balance between online processing (full online traversals) and offline computation (a materialized transitive closure). Last but not least, our open-source implementation of the RLC index can significantly speed up the processing of RLC queries in current mainstream graph engines.

  v

3 return true; 4 for

 4 (I ′ , I ′′ ) ∈ mergeJoin(Lout(s), L in (t)) do 5 if I ′ .mr = L and I ′′ .mr = L then

1

  procedure kernelBasedSearch(v, k) 2 for (L, vSet) ∈ backwardKernelSearch(v, k) do 3 backwardKernelBFS(v, vSet, L); 4 for (L, vSet) ∈ forwardKernelSearch(v, k) do 5 forwardKernelBFS(v, vSet, L); 6 procedure backwardKernelSearch(v, k) 7

12 for

 12 incoming edge e(y, x) to x do 13 seq ′ ← λ(e(y, x)) • seq; L ← MR(seq ′ ); 14 insert (y, v, L); 15 map.get(L).add(x); 16 if |seq ′ | < k then 17 q.enqueue(y, seq ′ ); 18 return map; 19 procedure insert(s, t, L) 20 if aid(t) > aid(s) or Query(s, t, L + ) then 21 return false;

22 else 23 add

 2223 (t, L) into Lout(s); 24 return true; 25 procedure backwardKernelBFS(v, vSet, L) 26

33 for

 33 incoming edge e(y, x) to x do 34 if l ̸ = λ(e(y, x)) or y was visited by state i then 35 continue; 36 if i = 1 and insert(y, v, L) then 37 continue; 38 q.enqueue(y, i); mark y visited by state i;

  Index size. The index size can be O(|V | 2 |L| k ) in the worst case, since each L in (v) or L out (v) can contain O(|V |C) index entries, where C = O(|L| k ) is the number of distinct minimum repeats for all label sequences derived from |L| of length up to k. C can be computed as follows, C= k i=1 F (i), where F (i) = |L| i -( j∈f (i),j̸ =i F (j)) with F (1) = |L| and f (i) the set of factors of integer i.Indexing time. In Algorithm 2, we perform a KBS from each vertex, and each KBS consists of two phases: the kernelsearch phase and the kernel-BFS phase. Performing a kernelsearch of depth k from a vertex requires O(|L| k |V | k ) time, and generates O(|L| k ) kernel candidates as discussed in the index size analysis. Each kernel candidate requires a kernel-BFS taking O(|E|k) time. Hence the time complexity for performing a KBS is O(|L| k |V | k + |L| k |E|k). The total index time is O(|V | k+1 |L| k + |L| k |V ||E|k) in the worst case.

Fig. 3 .

 3 Fig. 3. Execution time of 1000 true-queries or 1000 false-queries on real-world graphs.

Fig. 4 .

 4 Fig. 4. RLC index performance with different recursive k values.

TABLE I FREQUENTLY

 I USED SYMBOLS.

TABLE II THE

 II RLC INDEX FOR THE GRAPH IN

TABLE III OVERVIEW

 III OF REAL-WORLD GRAPHS.

	Dataset	|V |	|E|	|L|	Synthetic Labels	Loop Count	Triangle Count
	Advogato (AD) Soc-Epinions (EP) Twitter-ICWSM (TW) 465K 6K 75K Web-NotreDame (WN) 325K Web-Stanford (WS) 281K Web-Google (WG) 875K Wiki-Talk (WT) 2.3M Web-BerkStan (WB) 685K Wiki-hyperlink (WH) 1.7M Pokec (PR) 1.6M	51K 508K 834K 1.4M 2M 5M 5M 7M 28.5M 30.6M	3 8 8 8 8 8 8 8 8 8	√ √ √ √ √ √ √ √ √	4K 0 0 27K 0 0 0 0 4K 0	98K 1.6M 38K 8.9M 11M 13M 9M 64M 52M 32M
	StackOverflow (SO) LiveJournal (LJ) Wiki-link-fr (WF)	2.6M 4.8M 3.3M 123.7M 25 63.4M 3 68.9M 50	√ √	15M 0 19K	114M 285M 30B

  . We generate synthetic labels

		BFS	BiBFS	ETC	RLC Index
	10 3 10 4 10 5 10 6 10 7 10 8 10 9	Graphs AD EP TW WN WS WG WT WB WH PR SO LJ WF

TABLE IV INDEXING

 IV TIME (IT) AND INDEX SIZE (IS).

	Dataset	RLC Index	ETC
		IT (s) IS (MB)	IT (s) IS (MB)
	AD	0.7	1.9 2216.1	2798.7
	EP	22.6	29.3	-	-
	TW	8.1	93.5	-	-
	WN	33.1	122.6	-	-
	WS	53.5	173.9	-	-
	WG	101.3	403.6	-	-
	WT	812.9	607.1	-	-
	WB	167.1	474.2	-	-
	WH	3707.2	1319.1	-	-
	PR	3104.1	1212.6	-	-
	SO	57072.5	844.2	-	-
	LJ	18240.9	6248.1	-	-
	WF	51338.7	6467.9	-	-

  Fig. 5. Indexing time, index size, and execution time for graphs with |V | = 1M, varying d, and varying |L|.Fig. 6. Indexing time, index size, and query execution time for graphs with d = 5, |L| = 16, and varying |V |.

	Indexing Time (s) Indexing Time (s)	50 100 150 200 250 500 1000 1500	8 12 16 20 24 28 32 36 Label Set Size Indexing Time (ER) 8 12 16 20 24 28 32 36 Label Set Size Indexing Time (BA)	300 400 500 400 Index Size (MB) 600 800 Index Size (MB)	8 12 16 20 24 28 32 36 Label Set Size Index Size (ER) 8 12 16 20 24 28 32 36 Label Set Size Index Size (BA)	0.0 0.2 0.4 0.6 0.8 1.0 0.0 Execution Time (ms) 0.2 0.4 0.6 0.8 1.0 Execution Time (ms)	8 12 16 20 24 28 32 36 Label Set Size True-Queries (ER) 8 12 16 20 24 28 32 36 Label Set Size True-Queries (BA)	0.0 0.2 0.4 0.6 0.8 1.0 0.0 Execution Time (ms) 0.2 0.4 0.6 0.8 1.0 Execution Time (ms)	8 12 16 20 24 28 32 36 False-Queries (ER) Label Set Size 8 12 16 20 24 28 32 36 Label Set Size False-Queries (BA)
	Indexing Time (s)	10 2 10 1 10 2 10 3 10 4	10 3 Number of Vertices (thousands) Indexing Time ER BA	Index Size (MB)	10 2 10 2 10 3	10 3 Number of Vertices (thousands) Index Size ER	BA	Execution Time (ms)	10 2 10 1 10 0 10 1	10 3 Number of Vertices (thousands) Query Time (ER) ER.T ER.F	Execution Time (ms)	10 2 10 1 10 0 10 1	10 3 (thousands) Number of Vertices Query Time (BA) BA.T BA.F

TABLE V SPEED

 V -UPS (SU) AND WORKLOAD SIZE BREAK-EVEN POINTS (BEP) OF THE RLC INDEX OVER GRAPH ENGINES.

				RLC Query			Extended Query
	Sys.	Q1		Q2		Q3		Q4
		SU	BEP	SU	BEP	SU	BEP	SU	BEP
	Sys1	1200x 84100	10400x 34000	18400x	9400 34000x	300
	Sys2	3000x 34900 202000x 1700	1300000x	130 104000x	98
	Virtuoso 597x 180000	4900x	71700 38100000x	5	-	-

Open source code available at: https://github.com/g-rpqs/rlc-index