Abstract
Now more and more large graphs are available. One interesting problem is how to effectively find reachability between any vertex pairs in a very large graph. Multiple approaches have been proposed to answer reachability queries. However, most approaches only perform well on small graphs. Processing reachability queries on large graphs requires much storage and computation and still remains challenges. In this paper, we propose a scalable and fast indexing approach called Interval-Index, based on traversal tree-based partitioning and relabeling scheme. Our approach has several unique features: first, the traversal tree-based partitioning ensures access locality and parallelism in computation; second, continuous relabeling ensures fast querying and saves search space; third, we convert the entire graph database into a traversal tree graph on a smaller scale, to reach a compact storage structure. Finally, we run extensive experiments on synthetic graphs and real graphs with different sizes, and show that Interval-Index approach outperforms the state-of-the-art Feline in both storage size and the performance of query execution.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Jin, R., Ruan, N., Dey, S., Yu, J.X.: SCARAB: scaling reachability computation on large graphs. In: Proc. of SIGMOD 2012, pp. 169–180 (2012)
Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: Scalable reachability index for large graphs. PVLDB 3(1), 276–284 (2010)
Seufert, S., Anand, A., Bedathur, S.J., Weikum, G.: FERRARI: flexible and efficient reachability range assignment for graph indexing. In: Proc. of ICDE 2013, pp. 1009–1020 (2013)
Cheng, J., Huang, S.L., Wu, H.H., Fu, A.W.-C.: TF-label: a topological-folding labeling scheme for reachability querying in a large graph. In: Proc. of SIGMOD 2013, pp. 193–204 (2013)
Veloso, R., Cerf, L., Junior, W., Zaki, M.: Reachability queries in very large graphs: a fast refined online search approach. In: Proc. of EDBT 2014, pp. 511–522 (2014)
Yuan, P., Liu, P., Wu, B., Liu, L., Jin, H., Zhang, W.: TripleBit: a fast and compact system for large scale RDF data. PVLDB 6(7), 517–528 (2013)
Jin, R., Xiang, Y., Ruan, N., Fuhry, D.: 3-HOP: a high-compression indexing scheme for reachability query. In: Proc. of SIGMOD 1999, pp. 813–826 (2009)
Wei, H., Yu, J.X., Lu, C., Jin, R.M.: Reachability querying: An independent permutation labeling approach. PVLDB 7(12), 1191–1202 (2014)
Jin, R., Ruan, N., Xiang, Y., Wang, H.: Path-tree: An efficient reachability indexing scheme for large directed graphs. TODS 36(1), 7 (2011)
Schaik, S.J., Moor, O.D.: A memory efficient reachability data structure through bit vector compression. In: Proc. of SIGMOD 2011, pp. 913–924 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Li, F., Yuan, P., Jin, H. (2015). Interval-Index: A Scalable and Fast Approach for Reachability Queries in Large Graphs. In: Zhang, S., Wirsing, M., Zhang, Z. (eds) Knowledge Science, Engineering and Management. KSEM 2015. Lecture Notes in Computer Science(), vol 9403. Springer, Cham. https://doi.org/10.1007/978-3-319-25159-2_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-25159-2_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25158-5
Online ISBN: 978-3-319-25159-2
eBook Packages: Computer ScienceComputer Science (R0)