More Web Proxy on the site http://driver.im/

research-article

GRAIL: scalable reachability index for large graphs

Editors: Elisa Bertino, Paolo Atzeni, Kian Lee Tan, Yi Chen, Y. C. Tay Authors:

Hilmi Yildirim,

Mohammed J. ZakiAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 3, Issue 1-2

Pages 276 - 284

https://doi.org/10.14778/1920841.1920879

Published: 01 September 2010 Publication History

Abstract

Given a large directed graph, rapidly answering reachability queries between source and target nodes is an important problem. Existing methods for reachability trade-off indexing time and space versus query time performance. However, the biggest limitation of existing methods is that they simply do not scale to very large real-world graphs. We present a very simple, but scalable reachability index, called GRAIL, that is based on the idea of randomized interval labeling, and that can effectively handle very large graphs. Based on an extensive set of experiments, we show that while more sophisticated methods work better on small graphs, GRAIL is the only index that can scale to millions of nodes and edges. GRAIL has linear indexing time and space, and the query time ranges from constant time to being linear in the graph order and size.

References

[1]

R. Agrawal, A. Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. SIGMOD Rec., 18(2):253--262, 1989.

Digital Library

[2]

P. Bouros, S. Skiadopoulos, T. Dalamagas, D. Sacharidis, and T. Sellis. Evaluating reachability queries over path collections. In SSDBM, page 416, 2009.

Digital Library

[3]

R. Bramandia, B. Choi, and W. K. Ng. On incremental maintenance of 2-hop labeling of graphs. In WWW, 2008.

Digital Library

[4]

Y. Chen. General spanning trees and reachability query evaluation. In Canadian Conference on Computer Science and Software Engineering, Montreal, Quebec, Canada, 2009.

Digital Library

[5]

Y. Chen and Y. Chen. An efficient algorithm for answering graph reachability queries. In ICDE, 2008.

Digital Library

[6]

J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. Fast computing reachability labelings for large graphs with high compression rate. In EBDT, 2008.

Digital Library

[7]

E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. SIAM Journal of Computing, 32(5):1335--1355, 2003.

Digital Library

[8]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001.

Digital Library

[9]

C. Demetrescu and G. Italiano. Fully Dynamic Transitive Closure: Breaking through the O(n ²) Barrier. In FOCS, 2000.

Digital Library

[10]

C. Demetrescu and G. Italiano. Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures. Journal of Discrete Algorithms, 4(3):353--383, 2006.

[11]

P. F. Dietz. Maintaining order in a linked list. In STOC, 1982.

Digital Library

[12]

H. He, H. Wang, J. Yang, and P. S. Yu. Compact reachability labeling for graph-structured data. In CIKM, 2005.

Digital Library

[13]

H. V. Jagadish. A compression technique to materialize transitive closure. ACM Trans. Database Syst., 15(4):558--598, 1990.

Digital Library

[14]

R. Jin, Y. Xiang, N. Ruan, and D. Fuhry. 3-hop: a high-compression indexing scheme for reachability query. In SIGMOD, 2009.

Digital Library

[15]

R. Jin, Y. Xiang, N. Ruan, and H. Wang. Efficient answering reachability queries on very large directed graphs. In SIGMOD, 2008.

Digital Library

[16]

V. King and G. Sagert. A fully dynamic algorithm for maintaining the transitive closure. J. Comput. Syst. Sci., 65(1):150--167, 2002.

Digital Library

[17]

I. Krommidas and C. Zaroliagis. An experimental study of algorithms for fully dynamic transitive closure. Journal of Experimental Algorithmics, 12:16, 2008.

Digital Library

[18]

L. Roditty and U. Zwick. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In STOC, 2004.

Digital Library

[19]

R. Schenkel, A. Theobald, and G. Weikum. HOPI: an efficient connection index for complex XML document collections. In EBDT, 2004.

[20]

R. Schenkel, A. Theobald, and G. Weikum. Efficient creation and incremental maintenance of the hopi index for complex xml document collections. In ICDE, 2005.

Digital Library

[21]

S. Trissl and U. Leser. Fast and practical indexing and querying of very large graphs. In SIGMOD, 2007.

Digital Library

[22]

H. Wang, H. He, J. Yang, P. Yu, and J. X. Yu. Dual labeling: Answering graph reachability queries in constant time. In ICDE, 2006.

Digital Library

[23]

J. X. Yu, X. Lin, H. Wang, P. S. Yu, and J. Cheng. Fast computation of reachability labeling for large graphs. In EBDT, 2006.

Cited By

Chen XShi JPeng YLin WWang SZhang W(2024)Minimum Strongly Connected Subgraph Collection in Dynamic GraphsProceedings of the VLDB Endowment10.14778/3648160.364817317:6(1324-1336)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648173
Wang KCai MChen XLin XZhang WQin LZhang Y(2024)Efficient algorithms for reachability and path queries on temporal bipartite graphsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-024-00854-z33:5(1399-1426)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00778-024-00854-z
Meunier LZhao YRenz MNascimento M(2023)Reachability Queries on Dynamic Temporal Bipartite GraphsProceedings of the 31st ACM International Conference on Advances in Geographic Information Systems10.1145/3589132.3625647(1-11)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3589132.3625647
Show More Cited By

GRAIL: scalable reachability index for large graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

GRAIL: a scalable index for reachability queries in very large graphs

Given a large directed graph, rapidly answering reachability queries between source and target nodes is an important problem. Existing methods for reachability tradeoff indexing time and space versus query time performance. However, the biggest ...
GRAIL: efficient time-series representation learning

The analysis of time series is becoming increasingly prevalent across scientific disciplines and industrial applications. The effectiveness and the scalability of time-series mining techniques critically depend on design choices for three components ...
On the Multichromatic Number of s-Stable Kneser Graphs

For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 3, Issue 1-2

September 2010

1658 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 September 2010

Published in PVLDB Volume 3, Issue 1-2

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
633
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)4

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen XShi JPeng YLin WWang SZhang W(2024)Minimum Strongly Connected Subgraph Collection in Dynamic GraphsProceedings of the VLDB Endowment10.14778/3648160.364817317:6(1324-1336)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648173
Wang KCai MChen XLin XZhang WQin LZhang Y(2024)Efficient algorithms for reachability and path queries on temporal bipartite graphsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-024-00854-z33:5(1399-1426)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00778-024-00854-z
Meunier LZhao YRenz MNascimento M(2023)Reachability Queries on Dynamic Temporal Bipartite GraphsProceedings of the 31st ACM International Conference on Advances in Geographic Information Systems10.1145/3589132.3625647(1-11)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3589132.3625647
Zhang CBonifati AÖzsu MDas SPandis ISelçuk Candan KAmer-Yahia S(2023)An Overview of Reachability Indexes on GraphsCompanion of the 2023 International Conference on Management of Data10.1145/3555041.3589408(61-68)Online publication date: 4-Jun-2023
https://dl.acm.org/doi/10.1145/3555041.3589408
Chen YChen YZhang Y(2023)Evaluation of Reachability Queries Based on Recursive DAG DecompositionIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322019135:8(7935-7952)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3220191
He DYuan PJin H(2023)Answering reachability queries with ordered label constraints over labeled graphsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-022-2368-y18:1Online publication date: 12-Aug-2023
https://dl.acm.org/doi/10.1007/s11704-022-2368-y
Rani ARani K(2023)Parallel and Distributed Query Processing in Attributed NetworksMulti-disciplinary Trends in Artificial Intelligence10.1007/978-3-031-36402-0_11(124-134)Online publication date: 21-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36402-0_11
Shi QWang YYao PZhang C(2022)Indexing the extended Dyck-CFL reachability for context-sensitive program analysisProceedings of the ACM on Programming Languages10.1145/35633396:OOPSLA2(1438-1468)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563339
Hanauer KSchulz CTrummer J(2022)O’Reach: Even Faster Reachability in Large GraphsACM Journal of Experimental Algorithmics10.1145/355654027(1-27)Online publication date: 21-Oct-2022
https://dl.acm.org/doi/10.1145/3556540
Su ZWang DZhang XCui LMiao CSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)Efficient Reachability Query with Extreme Labeling FilterProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498446(966-975)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498446
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents