DBScholar

Back to papers

K-Reach: Who is in Your Small World

Summary: Introduces a simple, efficiently constructible index for exact k-hop reachability in directed graphs, a query class poorly served by transitive-closure and shortest-path indexes. Experiments show it outperforms state-of-the-art indexes, even for classic reachability. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
10554
Venue
VLDB
Year
2012
Pagerank
8.3982298e-05
Overall Rank
2,575 | 82.34%
DOI
10.14778/2350229.2350251

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{cheng_vldb12,
        title = {{K-Reach: Who is in Your Small World}},
        author = {Cheng, James and Shang, Zechao and Cheng, Hong and Wang, Haixun and Yu, Jeffrey Xu},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {11},
        pages = {1292--1303},
        doi = {10.14778/2350229.2350251},
        url = {https://doi.org/10.14778/2350229.2350251},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
927 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00013161079
1,123 Path Problems in Temporal Graphs 2014 VLDB 0.00012089975
1,432 The More the Merrier: Efficient Multi-Source Graph Traversal 2015 VLDB 0.0001080346
1,533 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010467148
1,622 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010201102
1,796 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 9.7380494e-05
2,874 iBFS: Concurrent Breadth-First Search on GPUs 2016 SIGMOD 8.0094569e-05
3,278 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.5712342e-05
4,474 Querying Big Graphs within Bounded Resources 2014 SIGMOD 6.6803983e-05
5,590 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 6.1557283e-05
8,650 Towards Generating Hop-constrained s-t Simple Path Graphs 2023 SIGMOD 5.3916003e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
269 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022786599
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
326 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00021152829
370 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019937972
444 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00018350865
674 Finding Maximal Cliques in Massive Networks by H*-graph 2010 SIGMOD 0.00015081844
679 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00015055389
746 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00014402233
1,254 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.0001147266
1,301 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011255351
2,490 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 8.5090456e-05
3,021 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 7.8401031e-05
3,857 Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012 SIGMOD 7.0678455e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,044 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB
2 9,132 HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs 2023 SIGMOD
3 2,490 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD
4 9,625 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB
5 6,603 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB
6 3,979 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB
7 7,322 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB
8 1,796 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD
9 269 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD
10 746 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD