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

He DYuan P(2025)TDS: fast answering reachability queries with hierarchical traversal treesCluster Computing10.1007/s10586-024-04814-828:3Online publication date: 21-Jan-2025
https://doi.org/10.1007/s10586-024-04814-8
Raghebi ZBanaei-Kashani F(2024)ActiveReach: an active learning framework for approximate reachability query answering in large-scale graphsFrontiers in Big Data10.3389/fdata.2024.14271047Online publication date: 19-Nov-2024
https://doi.org/10.3389/fdata.2024.1427104
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://dl.acm.org/doi/10.14778/3648160.3648173
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

100
Total Citations
View Citations
638
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)3

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

He DYuan P(2025)TDS: fast answering reachability queries with hierarchical traversal treesCluster Computing10.1007/s10586-024-04814-828:3Online publication date: 21-Jan-2025
https://doi.org/10.1007/s10586-024-04814-8
Raghebi ZBanaei-Kashani F(2024)ActiveReach: an active learning framework for approximate reachability query answering in large-scale graphsFrontiers in Big Data10.3389/fdata.2024.14271047Online publication date: 19-Nov-2024
https://doi.org/10.3389/fdata.2024.1427104
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://dl.acm.org/doi/10.14778/3648160.3648173
Sun YWang CFan GShi QZhang X(2024)Fast and Precise Static Null Exception Analysis With Synergistic PreprocessingIEEE Transactions on Software Engineering10.1109/TSE.2024.346655150:11(3022-3036)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3466551
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: 23-May-2024
https://dl.acm.org/doi/10.1007/s00778-024-00854-z
Tang XZhou JShi YLiu XKong L(2023)Efficient Reachability Ratio Computation for 2-Hop Labeling SchemeElectronics10.3390/electronics1205117812:5(1178)Online publication date: 28-Feb-2023
https://doi.org/10.3390/electronics12051178
Meunier LZhao YDamiani MRenz MEldawy AKröger PNascimento 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
Zhang CBonifati AKapp HHaprian VLozi J(2023)A Reachability Index for Recursive Label-Concatenated Graph Queries2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00013(67-81)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00013
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.

Figures

Tables

Media

View Issue’s Table of Contents