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)
Incoming Non-self Citations Over Time
Authors
- 1. Ruoming Jin (Kent State University)
- 2. Yang Xiang (Kent State University)
- 3. Ning Ruan (IBM; Kent State University)
- 4. Haixun Wang (IBM)
BibTeX Citation
@inproceedings{jin_sigmod08,
title = {{Efficiently Answering Reachability Queries on Very Large Directed Graphs}},
author = {Jin, Ruoming and Xiang, Yang and Ruan, Ning and Wang, Haixun},
series = {{SIGMOD} '08},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/1376616.1376677},
url = {https://dl.acm.org/doi/10.1145/1376616.1376677},
year = {2008}
}
Incoming Citations (Sorted by Pagerank)
Showing 27 of 27 citing papers.
Previous
Page 1 / 1
Next
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.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 282 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD | 0.0002242162 |
| 322 | Fast and Practical Indexing and Querying of Very Large Graphs | 2007 | SIGMOD | 0.00021275303 |
| 444 | Stack-based Algorithms for Pattern Matching on DAGs | 2005 | VLDB | 0.00018350865 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,278 | Simple, Fast, and Scalable Reachability Oracle | 2013 | VLDB |
| 2 | 2,575 | K-Reach: Who is in Your Small World | 2012 | VLDB |
| 3 | 5,044 | Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs | 2021 | VLDB |
| 4 | 3,857 | Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach | 2012 | SIGMOD |
| 5 | 7,322 | DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs | 2022 | VLDB |
| 6 | 6,603 | Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond | 2020 | VLDB |
| 7 | 3,979 | Reachability Querying: An Independent Permutation Labeling Approach | 2014 | VLDB |
| 8 | 9,625 | I/O Efficient Label-Constrained Reachability Queries in Large Graphs | 2024 | VLDB |
| 9 | 1,796 | Reachability Queries on Large Dynamic Graphs: A Total Order Approach | 2014 | SIGMOD |
| 10 | 2,490 | Computing Label-Constraint Reachability in Graph Databases | 2010 | SIGMOD |