Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs

Summary: FLoS provides exact top-k proximity via unified local search on random-walk measures. It uses no-local-optimum to derive monotone bounds that converge to exact results; generalizes across measures via cross-measure relations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4871
Venue: SIGMOD
Year: 2014
Pagerank: 0.00010090791
Overall Rank: 1,920 | 86.65%
DOI: 10.1145/2588555.2610500

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
1,013	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.00014645542
2,210	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.2856573e-05
2,537	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	8.5834428e-05
2,827	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.0551884e-05
3,709	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	6.8242482e-05
3,872	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	6.6785582e-05
4,733	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	5.9631943e-05
6,865	Indexed Fast Network Proximity Querying	2018	VLDB	4.9041884e-05
7,004	RAGraph: A Region-Aware Framework for Geo-Distributed Graph Processing	2024	VLDB	4.8656632e-05
7,193	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	4.8039257e-05
8,175	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.5676289e-05
8,375	Fast Neural Ranking on Bipartite Graph Indices	2022	VLDB	4.5326207e-05
10,703	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,641	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00011047924
2,098	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.5480012e-05
2,930	Assessing and Ranking Structural Correlations in Graphs	2011	SIGMOD	7.8723983e-05
4,527	On the Embeddability of Random Walk Distances	2013	VLDB	6.1083926e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,643	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3928286e-05
6,503	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	5.0357715e-05
10,171	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD	4.1945683e-05
1,285	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012833377
5,946	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2616887e-05
7,277	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7794907e-05
4,791	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9188595e-05
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
8,505	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.4958064e-05
1,641	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00011047924