Lucien D.J. Valstar
ABSTRACT
Consider a directed edge-labeled graph, such as a social network or a citation network. A fundamental query on such data is to determine if there is a path in the graph from a given source vertex to a given target vertex, using only edges with labels in a restricted subset of the edge labels in the graph. Such label-constrained reachability (LCR) queries play an important role in graph analytics, for example, as a core fragment of the so-called regular path queries which are supported in practical graph query languages such as the W3C's SPARQL 1.1, Neo4j's Cypher, and Oracle's PGQL. Current solutions for LCR evaluation, however, do not scale to large graphs which are increasingly common in a broad range of application domains. In this paper we present the first practical solution for efficient LCR evaluation, leveraging landmark-based indexes for large graphs. We show through extensive experiments that our indexes are significantly smaller than state-of-the-art LCR indexing techniques, while supporting up to orders of magnitude faster query evaluation times. Our complete C++ codebase is available as open source for further research.
- T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD, pages 349--360, 2013. Google Scholar
Digital Library
- T. Akiba, Y. Iwata, and Y. Yoshida. Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In WWW, pages 237--248, 2014. Google ScholarDigital Library
- A. Anand, S. Seufert, S. Bedathur, and G. Weikum. FERRARI: Flexible and efficient reachability range assignment for graph indexing. In ICDE, pages 1009--1020, 2013. Google ScholarDigital Library
- R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter, and D. Vrgoc. Foundations of modern graph query languages. CoRR, abs/1610.06264, 2016.Google Scholar
- P. Baeza. Querying graph databases. In PODS, pages 175--188, 2013. Google ScholarDigital Library
- G. Bagan, A. Bonifati, R. Ciucanu, G. H. L. Fletcher, A. Lemay, and N. Advokaat. gMark: Schema-driven generation of graphs and queries. IEEE Transactions on Knowledge and Data Engineering, 2017 (to appear). Preprint at http://arxiv.org/abs/1511.08386. Google ScholarDigital Library
- C. Barrett, R. Jacob, and M. Marathe. Formal-language-constrained path problems. SIAM Journal on Computing, 30(3):809--837, 2000. Google ScholarDigital Library
- S. Beamer, K. Asanovic, and D. A. Patterson. Direction-optimizing breadth-first search. Scientific Programming, 21(3--4):137--148, 2013. Google ScholarDigital Library
- F. Bonchi, A. Gionis, F. Gullo, and A. Ukkonen. Distance oracles in edge-labeled graphs. In EDBT, pages 547--548, 2014.Google Scholar
- M. Chen, Y. Gu, Y. Bao, and G. Yu. Label and distance-constraint reachability queries in uncertain graphs. In DASFAA, pages 188--202, 2014.Google ScholarCross Ref
- J. Cheng, S. Huang, H. Wu, and A. W.-C. Fu. TF-label: a topological-folding labeling scheme for reachability querying in a large graph. In SIGMOD, pages 193--204, 2013. Google ScholarDigital Library
- J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. Fast computation of reachability labeling for large graphs. In EDBT, pages 961--979, 2006. Google ScholarDigital Library
- E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5):1338--1355, 2003. Google ScholarDigital Library
- G. H. L. Fletcher, J. Peters, and A. Poulovassilis. Efficient regular path query evaluation using path indexes. In EDBT, pages 636--639, 2016.Google Scholar
- R. Geisberger, M. N. Rice, P. Sanders, and V. J. Tsotras. Route planning with flexible edge restrictions. ACM JEA, 17(1), 2012. Google ScholarDigital Library
- A. Gubichev et al. Sparqling kleene: fast property paths in RDF-3X. In GRADES, 2013. Google ScholarDigital Library
- R. Jin, H. Hong, H. Wang, N. Ruan, and Y. Xiang. Computing label-constraint reachability in graph databases. In SIGMOD, pages 123--134, 2010. Google ScholarDigital Library
- R. Jin, N. Ruan, S. Dey, and J. Y. Xu. SCARAB: scaling reachability computation on large graphs. In SIGMOD, pages 169--180, 2012. Google ScholarDigital Library
- R. Jin and G. Wang. Simple, fast, and scalable reachability oracle. PVLDB, 6(14):1978--1989, 2013. Google ScholarDigital Library
- P. Klodt. Indexing strategies for constrained shortest paths over large social networks. BSc thesis, Universität des Saarlandes, 2011.Google Scholar
- J. Kunegis. KONECT - the koblenz network collection. In Proc. Int. Conf. on World Wide Web Companion, pages 1343--1350, Koblenz, 2013. Google ScholarDigital Library
- J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.Google Scholar
- J. Leskovec and R. SosiČ. SNAP: A general purpose network analysis and graph mining library in C++. http://snap.stanford.edu/snap, June 2014.Google Scholar
- A. Likhyani and S. Bedathur. Label constrained shortest path estimation. In CIKM, pages 1177--1180, 2013. Google ScholarDigital Library
- R. Schenkel, A. Theobald, and G. Weikum. HOPI: An efficient connection index for complex XML document collections. In EDBT, pages 237--255, 2004.Google ScholarCross Ref
- K. Simon. An improved algorithm for transitive closure on acyclic digraphs. Theoretical Computer Science, 58(1):325--346, 1988. Google ScholarDigital Library
- E. Sperner. Ein satz über untermengen einer endlichen menge. Math. Z., 27(1):544--548, 1928.Google ScholarCross Ref
- O. van Rest, S. Hong, J. Kim, X. Meng, and H. Chafi. PGQL: a property graph query language. In GRADES, 2016. Google ScholarDigital Library
- S. van Schaik and O. de Moor. A memory efficient reachability data structure through bit vector compression. In SIGMOD, pages 913--924, 2011. Google ScholarDigital Library
- H. Wei, J. X. Yu, C. Lu, and R. Jin. Reachability querying: an independent permutation labeling approach. PVLDB, 7(12):1191--1202, 2014. Google ScholarDigital Library
- P. T. Wood. Query languages for graph databases. ACM SIGMOD Record, 41(1):50--60, 2012. Google ScholarDigital Library
- N. Yakovets, P. Godfrey, and J. Gryz. Query planning for evaluating SPARQL property paths. In SIGMOD, pages 1875--1889, 2016. Google ScholarDigital Library
- Y. Yano, T. Akiba, Y. Iwata, and Y. Yoshida. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In CIKM, pages 1601--1606, 2013. Google ScholarDigital Library
- H. Yildirim, V. Chaoji, and M. Zaki. GRAIL: Scalable reachability index for large graphs. PVLDB, 3(1--2):276--284, 2010. Google ScholarDigital Library
- J. X. Yu and J. Cheng. Graph reachability queries: A survey. In Managing and Mining Graph Data. Springer, 2010.Google ScholarCross Ref
- Z. Zhang, J. Yu, L. Qin, Q. Zhu, and X. Zhou. I/O cost minimization: reachability queries processing over massive graphs. In EDBT, pages 468--479, 2012. Google ScholarDigital Library
- L. Zou, K. Xu, J. X. Yu, L. Chen, Y. Xiao, and D. Zhao. Efficient processing of label-constraint reachability queries in large graphs. Information Systems, 40:47--66, 2014. Google ScholarDigital Library
Recommendations
Answering billion-scale label-constrained reachability queries within microsecond
In this paper, we study the problem of label-constrained reachability (LCR) query which is fundamental in many applications with directed edge-label graphs. Although the classical reachability query (i.e., reachability query without label constraint) ...
Graph Indexing for Efficient Evaluation of Label-constrained Reachability Queries
Best of PODS 2019 and Regular PapersGiven a directed edge labeled graph G, to check whether vertex v is reachable from vertex u under a label set S is to know if there is a path from u to v whose edge labels across the path are a subset of S. Such a query is referred to as a label-...
Efficiently Answering Regular Simple Path Queries on Large Labeled Networks
SIGMOD '19: Proceedings of the 2019 International Conference on Management of DataA fundamental query in labeled graphs is to determine if there exists a path between a given source and target vertices, such that the path satisfies a given label constraint. One of the powerful forms of specifying label constraints is through regular ...
Comments