Answering reachability and K-reach queries on large graphs with label constraints

The purpose of this paper is to examine the problem of label-constrained reachability (LCR) and K-reach (LCKR) queries, which are fundamental in a wide variety of applications using directed edge-labeled graphs. While reachability and K-reach queries have been extensively researched, LCR and LCKR queries are much more challenging due to the fact that the number of potential label-constraint sets is exponential to the size of the labels. We note that existing techniques for LCR queries only build a partial index and that their worse-case query time could be comparable to that of an online breadth-first search (BFS). This paper proposes a new label-constrained 2-hop indexing method with innovative pruning rules and order strategies. Our work demonstrates that the worst query time could be bounded by the number of in-out index entries. Extensive experiments demonstrate that the proposed methods substantially outperform the state-of-the-art approach in terms of the query response time (up to 5 orders of magnitude speedup), index size, and the index construction time. More precisely, the method we present can response LCR queries across billion-scale networks within microseconds on a single machine. We formally define the problem of LCKR queries and discuss critical applications for addressing it. To tackle the difficulties presented by label and hop constraints, an efficient upper and lower bound is suggested based on a search method. Using all of these techniques, extensive experiments on synthetic and real-world networks demonstrate that our algorithm outperforms the baseline by about three to four orders of magnitude while maintaining competitive indexing time and size.