K-Reach: Who is in Your Small World

Summary: K-Reach is a simple, easy-to-build index for answering k-hop reachability queries in directed graphs. Experiments show it outperforms state-of-the-art reachability indexes and remains efficient for both classic and k-hop queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10366
Venue: VLDB
Year: 2012
Pagerank: 8.1682536e-05
Overall Rank: 2,756 | 80.83%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,024	Path Problems in Temporal Graphs	2014	VLDB	0.00014609643
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
1,665	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010967716
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
3,233	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	7.3361904e-05
3,671	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8560247e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
5,479	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	5.4850984e-05
8,668	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD	4.4718257e-05

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
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025097452
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023598882
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
733	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017460741
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
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
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
4,067	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4795399e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,540	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4498271e-05
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
9,042	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	4.4039656e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1506256e-05
7,428	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7320892e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034