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
4167
Venue
SIGMOD
Year
2009
Pagerank
0.00029092277
Overall Rank
280 | 98.06%
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
377 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025074538
502 On Graph Query Optimization in Large Networks 2010 VLDB 0.00021528261
645 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018727714
727 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00017462279
1,385 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012259478
1,419 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00012072488
1,448 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011928845
1,551 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011395294
1,570 KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs 2020 VLDB 0.00011311977
1,572 Query Preserving Graph Compression 2012 SIGMOD 0.00011296109
1,776 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.0001058029
1,879 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010227906
2,043 Local Algorithms for Hierarchical Dense Subgraph Discovery 2019 VLDB 9.6970812e-05
2,762 K-Reach: Who is in Your Small World 2012 VLDB 8.1614818e-05
2,913 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 7.9229304e-05
2,958 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8126329e-05
3,130 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 7.5054361e-05
3,155 Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs 2022 VLDB 7.4700348e-05
3,235 iBFS: Concurrent Breadth-First Search on GPUs 2016 SIGMOD 7.3298263e-05
3,579 Finding Locally Densest Subgraphs: A Convex Programming Approach 2022 VLDB 6.9461197e-05
3,643 On Querying Historical Evolving Graph Sequences 2011 VLDB 6.8856861e-05
3,676 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8500097e-05
4,478 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.1452192e-05
5,488 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 5.4798261e-05
5,548 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4445937e-05
5,816 An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010 SIGMOD 5.3158435e-05
6,531 Labeling Workflow Views with Fine-Grained Dependencies 2012 VLDB 5.0196961e-05
6,660 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 4.9672425e-05
6,796 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9195203e-05
7,588 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.6996269e-05
7,595 DAG Reduction: Fast Answering Reachability Queries 2017 SIGMOD 4.6980168e-05
7,714 Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024 VLDB 4.6651585e-05
7,863 Adaptive Optimizations of Recursive Queries in Teradata 2012 SIGMOD 4.628688e-05
8,056 Labeling Recursive Workflow Executions On-the-Fly 2011 SIGMOD 4.5903524e-05
9,409 A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3399748e-05
9,485 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 4.3300131e-05
9,557 An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3212967e-05
10,526 Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum 2025 SIGMOD 4.1905499e-05
10,689 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.1905499e-05
10,869 Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs 2025 VLDB 4.1905499e-05
10,988 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.1905499e-05
11,051 Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs 2024 VLDB 4.1905499e-05
11,201 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 4.1905499e-05
11,305 Density Personalized Group Query 2023 VLDB 4.1905499e-05
11,413 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1905499e-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