DBScholar

Back to papers

Simple, Fast, and Scalable Reachability Oracle

Summary: Introduces Hierarchical- and Distribution-Labeling reachability oracles that avoid transitive-closure materialization and costly set cover. On massive real-world graphs, they construct an order of magnitude faster while outperforming closure compression and online search in index size and query speed. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h08770361fdbe9c49
Venue
VLDB
Year
2013
Pagerank
7.3926236e-05
Overall Rank
3,348 | 77.50%
DOI
10.14778/2556549.2556578

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{jin_vldb13,
        title = {{Simple, Fast, and Scalable Reachability Oracle}},
        author = {Jin, Ruoming and Wang, Guan},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {1978--1989},
        doi = {10.14778/2556549.2556578},
        url = {https://doi.org/10.14778/2556549.2556578},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank Citing Paper Year Venue Pagerank
937 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00012977594
1,849 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 9.5068688e-05
2,734 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.0789676e-05
4,049 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.8302372e-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,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
9,303 HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs 2023 SIGMOD 5.1978865e-05
9,805 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 5.1257999e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank Cited Paper Year Venue Pagerank
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025584127
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
453 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00017972038
693 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00014734389
774 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00014083518
1,260 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011296964
1,329 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011000029
1,563 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010224369
1,647 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 9.9875545e-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
5,152 Performance Guarantees for Distributed Reachability Queries 2012 VLDB 6.2525917e-05
5,528 Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets 2012 VLDB 6.0935715e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,765 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB
2 7,351 Toward a Distance Oracle for Billion-Node Graphs 2014 VLDB
3 8,789 Distributed Set Reachability 2016 SIGMOD
4 1,563 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD
5 6,177 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB
6 1,849 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD
7 2,534 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD
8 9,805 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB
9 4,049 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB
10 774 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD