DBScholar

Back to papers

GRAIL: Scalable Reachability Index for Large Graphs

Summary: GRAIL uses randomized interval labeling to build a scalable reachability index for massive directed graphs. Linear indexing time/space; query time ranges from constant to linear, enabling reachability on graphs with millions of nodes/edges where prior methods fail to scale. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hb33faa2b93a577b8
Venue
VLDB
Year
2010
Pagerank
0.00014734389
Overall Rank
693 | 95.35%
DOI
10.14778/1920841.1920880

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{yldrm_vldb10,
        title = {{GRAIL: Scalable Reachability Index for Large Graphs}},
        author = {Yıldırım, Hilmi and Chaoji, Vineet and Zaki, Mohammed J.},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {276--284},
        doi = {10.14778/1920841.1920880},
        url = {https://doi.org/10.14778/1920841.1920880},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank Citing Paper Year Venue Pagerank
937 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00012977594
1,260 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011296964
1,375 Query Preserving Graph Compression 2012 SIGMOD 0.00010877488
1,563 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010224369
1,849 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 9.5068688e-05
2,257 Regular Path Query Evaluation on Streaming Graphs 2020 SIGMOD 8.7434588e-05
2,563 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 8.2934229e-05
2,604 K-Reach: Who is in Your Small World 2012 VLDB 8.2302549e-05
2,734 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.0789676e-05
2,789 iBFS: Concurrent Breadth-First Search on GPUs 2016 SIGMOD 8.0116036e-05
3,154 Managing Large Dynamic Graphs Efficiently 2012 SIGMOD 7.5870734e-05
3,348 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.3926236e-05
4,049 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.8302372e-05
5,000 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3202341e-05
5,528 Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets 2012 VLDB 6.0935715e-05
5,554 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.0858703e-05
5,717 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 6.0191048e-05
6,177 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.8598586e-05
7,237 Labeling Workflow Views with Fine-Grained Dependencies 2012 VLDB 5.5785819e-05
7,724 Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024 VLDB 5.4672516e-05
7,840 DAG Reduction: Fast Answering Reachability Queries 2017 SIGMOD 5.442834e-05
8,193 Labeling Recursive Workflow Executions On-the-Fly 2011 SIGMOD 5.3803708e-05
8,789 Distributed Set Reachability 2016 SIGMOD 5.2767294e-05
10,247 Top-k Relevant Semantic Place Retrieval on Spatial RDF Data 2016 SIGMOD 5.0525742e-05
12,530 I/O Efficient: Computing SCCs in Massive Graphs 2013 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
274 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022490994
294 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00021927874
330 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00020838159
774 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00014083518
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,534 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD
2 6,177 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB
3 9,805 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB
4 2,604 K-Reach: Who is in Your Small World 2012 VLDB
5 3,348 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB
6 4,049 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB
7 774 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD
8 1,849 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD
9 330 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD
10 2,563 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD