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: 4872
Venue: SIGMOD
Year: 2014
Pagerank: 0.00010130702
Overall Rank: 1,907 | 86.75%
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
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
1,014	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.00014631717
2,189	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.3358152e-05
2,515	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	8.6115215e-05
2,522	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.6029608e-05
3,715	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	6.8176818e-05
3,853	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	6.6987268e-05
4,688	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	5.9900111e-05
6,866	Indexed Fast Network Proximity Querying	2018	VLDB	4.8994824e-05
6,970	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	4.8740302e-05
7,003	RAGraph: A Region-Aware Framework for Geo-Distributed Graph Processing	2024	VLDB	4.8609956e-05
7,827	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.6379617e-05
8,373	Fast Neural Ranking on Bipartite Graph Indices	2022	VLDB	4.5282739e-05
10,711	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1905499e-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,626	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.0001108491
2,076	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.6057342e-05
2,930	Assessing and Ranking Structural Correlations in Graphs	2011	SIGMOD	7.8790753e-05
4,487	On the Embeddability of Random Walk Distances	2013	VLDB	6.1412716e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,656	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3876479e-05
6,497	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	5.0324877e-05
10,171	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD	4.1905499e-05
1,280	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012838714
5,945	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2583364e-05
7,271	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7764555e-05
1,159	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00013584223
4,760	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9342555e-05
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05
1,626	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.0001108491