Back to papers
Efficiently Answering Reachability Queries on Very Large Directed Graphs
Summary: Introduces path-tree, a tree-shaped spanning subgraph to aid reachability labeling on very large directed graphs. Path-tree cover yields scalable reachability labels and outperforms traditional interval/2-hop approaches, with analytic and empirical validation.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 4018
- Venue
- SIGMOD
- Year
- 2008
- Pagerank
- 0.00016650034
- Overall Rank
- 788 | 94.52%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 27 of 27 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 279 |
3-HOP: A High-Compression Indexing Scheme for Reachability Query |
2009 |
SIGMOD |
0.00029113513 |
| 376 |
TEDI: Efficient Shortest Path Query Answering on Graphs |
2010 |
SIGMOD |
0.00025097452 |
| 506 |
On Graph Query Optimization in Large Networks |
2010 |
VLDB |
0.00021475362 |
| 733 |
GRAIL: Scalable Reachability Index for Large Graphs |
2010 |
VLDB |
0.00017460741 |
| 1,553 |
A Memory Efficient Reachability Data Structure Through Bit Vector Compression |
2011 |
SIGMOD |
0.00011402871 |
| 1,579 |
Query Preserving Graph Compression |
2012 |
SIGMOD |
0.00011283792 |
| 1,777 |
Reachability Queries on Large Dynamic Graphs: A Total Order Approach |
2014 |
SIGMOD |
0.00010589591 |
| 2,756 |
K-Reach: Who is in Your Small World |
2012 |
VLDB |
8.1682536e-05 |
| 2,957 |
Computing Label-Constraint Reachability in Graph Databases |
2010 |
SIGMOD |
7.8198686e-05 |
| 3,127 |
SCARAB: Scaling Reachability Computation on Large Graphs |
2012 |
SIGMOD |
7.5046522e-05 |
| 3,232 |
Managing Large Dynamic Graphs Efficiently |
2012 |
SIGMOD |
7.336861e-05 |
| 3,671 |
Simple, Fast, and Scalable Reachability Oracle |
2013 |
VLDB |
6.8560247e-05 |
| 4,478 |
Reachability Querying: An Independent Permutation Labeling Approach |
2014 |
VLDB |
6.1506256e-05 |
| 4,836 |
Making Graphs Compact by Lossless Contraction |
2021 |
SIGMOD |
5.8896897e-05 |
| 5,479 |
Microblog Entity Linking with Social Temporal Context |
2015 |
SIGMOD |
5.4850984e-05 |
| 5,802 |
An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels |
2010 |
SIGMOD |
5.3209459e-05 |
| 6,657 |
On Querying Historical Connectivity in Temporal Graphs |
2024 |
SIGMOD |
4.9720132e-05 |
| 6,730 |
A Hierarchical Contraction Scheme for Querying Big Graphs |
2022 |
SIGMOD |
4.9479867e-05 |
| 7,428 |
DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs |
2022 |
VLDB |
4.7320892e-05 |
| 7,596 |
DAG Reduction: Fast Answering Reachability Queries |
2017 |
SIGMOD |
4.7016964e-05 |
| 7,716 |
Minimum Strongly Connected Subgraph Collection in Dynamic Graphs |
2024 |
VLDB |
4.6696364e-05 |
| 7,863 |
Adaptive Optimizations of Recursive Queries in Teradata |
2012 |
SIGMOD |
4.6328993e-05 |
| 8,054 |
Labeling Recursive Workflow Executions On-the-Fly |
2011 |
SIGMOD |
4.5947587e-05 |
| 9,042 |
HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs |
2023 |
SIGMOD |
4.4039656e-05 |
| 9,738 |
The Space-Efficient Core of Vadalog |
2019 |
PODS |
4.2936538e-05 |
| 11,031 |
Poligras: Policy-based Graph Summarization |
2024 |
VLDB |
4.1945683e-05 |
| 11,503 |
Preference Queries over Taxonomic Domains |
2021 |
VLDB |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 3,671 |
Simple, Fast, and Scalable Reachability Oracle |
2013 |
VLDB |
6.8560247e-05 |
| 2,756 |
K-Reach: Who is in Your Small World |
2012 |
VLDB |
8.1682536e-05 |
| 5,540 |
Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs |
2021 |
VLDB |
5.4498271e-05 |
| 4,067 |
Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach |
2012 |
SIGMOD |
6.4795399e-05 |
| 7,428 |
DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs |
2022 |
VLDB |
4.7320892e-05 |
| 6,795 |
Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond |
2020 |
VLDB |
4.9242446e-05 |
| 4,478 |
Reachability Querying: An Independent Permutation Labeling Approach |
2014 |
VLDB |
6.1506256e-05 |
| 9,483 |
I/O Efficient Label-Constrained Reachability Queries in Large Graphs |
2024 |
VLDB |
4.3341665e-05 |
| 1,777 |
Reachability Queries on Large Dynamic Graphs: A Total Order Approach |
2014 |
SIGMOD |
0.00010589591 |
| 2,957 |
Computing Label-Constraint Reachability in Graph Databases |
2010 |
SIGMOD |
7.8198686e-05 |