Database Paper Browser

Back to papers

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)

Paper ID
4166
Venue
SIGMOD
Year
2009
Pagerank
0.00029113513
Overall Rank
279 | 98.07%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 45 of 45 citing papers.

Rank Citing Paper Year Venue Pagerank
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
644 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018748988
733 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00017460741
1,378 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012294512
1,414 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00012118275
1,450 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011925844
1,553 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011402871
1,570 KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs 2020 VLDB 0.00011322927
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
1,880 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010226347
2,039 Local Algorithms for Hierarchical Dense Subgraph Discovery 2019 VLDB 9.7061003e-05
2,756 K-Reach: Who is in Your Small World 2012 VLDB 8.1682536e-05
2,909 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 7.9305767e-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,146 Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs 2022 VLDB 7.477231e-05
3,233 iBFS: Concurrent Breadth-First Search on GPUs 2016 SIGMOD 7.3361904e-05
3,575 Finding Locally Densest Subgraphs: A Convex Programming Approach 2022 VLDB 6.9528126e-05
3,639 On Querying Historical Evolving Graph Sequences 2011 VLDB 6.8913642e-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
5,479 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 5.4850984e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
5,802 An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010 SIGMOD 5.3209459e-05
6,533 Labeling Workflow Views with Fine-Grained Dependencies 2012 VLDB 5.0245193e-05
6,657 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 4.9720132e-05
6,795 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9242446e-05
7,584 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.7041255e-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,403 A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3441378e-05
9,483 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 4.3341665e-05
9,557 An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3254416e-05
10,517 Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum 2025 SIGMOD 4.1945683e-05
10,681 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.1945683e-05
10,865 Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs 2025 VLDB 4.1945683e-05
10,985 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.1945683e-05
11,048 Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs 2024 VLDB 4.1945683e-05
11,199 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 4.1945683e-05
11,303 Density Personalized Group Query 2023 VLDB 4.1945683e-05
11,410 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1945683e-05
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.

Previous Page 1 / 1 Next

Semantically Similar Papers