3-HOP: A High-Compression Indexing Scheme for Reachability Query
Summary: 3-HOP: high-compression index scheme for reachability in dense DAGs. Uses chain structures plus hops to minimize index size; develops near-optimal transitive-closure contour, with much smaller index than 2-hop/path-tree and competitive query times. (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 (Kent State University)
- 4. David Fuhry (Kent State University)
BibTeX Citation
@inproceedings{jin_sigmod09,
title = {{3-HOP: A High-Compression Indexing Scheme for Reachability Query}},
author = {Jin, Ruoming and Xiang, Yang and Ruan, Ning and Fuhry, David},
series = {{SIGMOD} '09},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/1559845.1559930},
url = {https://dl.acm.org/doi/10.1145/1559845.1559930},
year = {2009}
}Incoming Citations (Sorted by Pagerank)
Showing 47 of 47 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 293 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD | 0.00021884281 |
| 331 | Fast and Practical Indexing and Querying of Very Large Graphs | 2007 | SIGMOD | 0.00020800828 |
| 456 | Stack-based Algorithms for Pattern Matching on DAGs | 2005 | VLDB | 0.00017946233 |
| 499 | Efficient Aggregation for Graph Summarization | 2008 | SIGMOD | 0.00017292147 |
| 601 | Substructure Similarity Search in Graph Databases | 2005 | SIGMOD | 0.00015699993 |
| 779 | Efficiently Answering Reachability Queries on Very Large Directed Graphs | 2008 | SIGMOD | 0.00014049427 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,061 | PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration | 2021 | SIGMOD |
| 2 | 6,192 | Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond | 2020 | VLDB |
| 3 | 6,786 | DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs | 2022 | VLDB |
| 4 | 1,859 | Reachability Queries on Large Dynamic Graphs: A Total Order Approach | 2014 | SIGMOD |
| 5 | 7,861 | DAG Reduction: Fast Answering Reachability Queries | 2017 | SIGMOD |
| 6 | 1,577 | Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks | 2014 | VLDB |
| 7 | 2,541 | Computing Label-Constraint Reachability in Graph Databases | 2010 | SIGMOD |
| 8 | 1,341 | A Memory Efficient Reachability Data Structure Through Bit Vector Compression | 2011 | SIGMOD |
| 9 | 779 | Efficiently Answering Reachability Queries on Very Large Directed Graphs | 2008 | SIGMOD |
| 10 | 2,617 | K-Reach: Who is in Your Small World | 2012 | VLDB |