Abstract
As a fundamental task in graph data mining, answering k-hop reachability queries is useful in many applications such as analysis of social networks and biological networks. Most of the existing methods for processing such queries can only deal with directed acyclic graphs (DAGs). However, cycles are ubiquitous in lots of real-world graphs. Furthermore, they may require unacceptable indexing space or expensive online search time when the input graph becomes very large. In order to solve k-hop reachability queries for large general directed graphs, we propose a practical and efficient method named ESTI (Extended Spanning Tree Index). It constructs an extended spanning tree in the offline phase and speeds up online querying based on three carefully designed pruning rules over the built index. Extensive experiments show that ESTI significantly outperforms the state-of-art in online querying, while ensuring a linear index size and stable index construction time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cheng, J., Shang, Z., Cheng, H., Wang, H., Yu, J.X.: K-reach: who is in your small world. CoRR abs/1208.0090 (2012)
Cheng, J., Shang, Z., Cheng, H., Wang, H., Yu, J.X.: Efficient processing of k-hop reachability queries. VLDB J. 23(2), 227–252 (2014)
Du, M., Yang, A., Zhou, J., Tang, X., Chen, Z., Zuo, Y.: HT: a novel labeling scheme for k-hop reachability queries on DAGs. IEEE Access 7, 172110–172122 (2019)
Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: SIGMOD 2008, pp. 595–608 (2008)
Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection
van Schaik, S.J., de Moor, O.: A memory efficient reachability data structure through bit vector compression. In: SIGMOD 2011, pp. 913–924 (2011)
Seufert, S., Anand, A., Bedathur, S., Weikum, G.: Ferrari: flexible and efficient reachability range assignment for graph indexing (2013)
Su, J., Zhu, Q., Wei, H., Yu, J.X.: Reachability querying: can it be even faster? IEEE Trans. Knowl. Data Eng. 29(3), 683–697 (2017)
Trißl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: SIGMOD 2007, pp. 845–856 (2007)
Veloso, R.R., Cerf, L., Meira Jr., W., Zaki, M.J.: Reachability queries in very large graphs: a fast refined online search approach. In: EDBT, pp. 511–522 (2014)
Wei, H., Yu, J.X., Lu, C., Jin, R.: Reachability querying: an independent permutation labeling approach. Proc. VLDB Endow. 7(12), 1191–1202 (2014)
Xie, X., Yang, X., Wang, X., Jin, H., Wang, D., Ke, X.: BFSI-B: an improved k-hop graph reachability queries for cyber-physical systems. Inf. Fusion 38, 35–42 (2017)
Yildirim, H., Chaoji, V., Zaki, M.: Grail: a scalable index for reachability queries in very large graphs. VLDB J. 21, 1–26 (2012)
Zhou, L., Chen, R., Xia, Y., Teodorescu, R.: C-graph: a highly efficient concurrent graph reachability query framework. In: ICPP, pp. 79:1–79:10. ACM (2018)
Acknowledgments
This work was supported by National Natural Science Foundation of China (Grant No. 61902074) and Science and Technology Committee Shanghai Municipality (Grant No. 19ZR1404900).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Cai, Y., Zheng, W. (2021). ESTI: Efficient k-Hop Reachability Querying over Large General Directed Graphs. In: Jensen, C.S., et al. Database Systems for Advanced Applications. DASFAA 2021 International Workshops. DASFAA 2021. Lecture Notes in Computer Science(), vol 12680. Springer, Cham. https://doi.org/10.1007/978-3-030-73216-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-73216-5_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-73215-8
Online ISBN: 978-3-030-73216-5
eBook Packages: Computer ScienceComputer Science (R0)