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: hee186e305af8d2b3
Venue: SIGMOD
Year: 2014
Pagerank: 0.00010095949
Overall Rank: 1,604 | 89.22%
DOI: 10.1145/2588555.2610500

Incoming Non-self Citations Over Time

Authors

1. Yubao Wu (Case Western Reserve University)
2. Ruoming Jin (Kent State University)
3. Xiang Zhang (Case Western Reserve University)

BibTeX Citation

@inproceedings{wu_sigmod14,
        title = {{Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs}},
        author = {Wu, Yubao and Jin, Ruoming and Zhang, Xiang},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2610500},
        url = {https://dl.acm.org/doi/10.1145/2588555.2610500},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
830	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.00013605481
1,798	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.616919e-05
2,102	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0463758e-05
2,183	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.8962182e-05
3,017	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.7471344e-05
3,266	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.4775e-05
4,101	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.8073016e-05
6,785	Indexed Fast Network Proximity Querying	2018	VLDB	5.6823069e-05
6,867	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	5.6599424e-05
6,895	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.6536466e-05
7,000	RAGraph: A Region-Aware Framework for Geo-Distributed Graph Processing	2024	VLDB	5.6251489e-05
8,394	Fast Neural Ranking on Bipartite Graph Indices	2022	VLDB	5.3407629e-05
9,551	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.1591583e-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,419	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010728945
1,860	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.4876834e-05
3,196	Assessing and Ranking Structural Correlations in Graphs	2011	SIGMOD	7.5460261e-05
4,649	On the Embeddability of Random Walk Distances	2013	VLDB	6.4863785e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,264	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB
2	6,107	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
3	10,647	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
4	1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD
5	5,914	Reverse Top-k Search using Random Walk with Restart	2014	VLDB
6	7,075	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD
7	4,303	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
8	1,063	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB
9	8,662	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
10	1,419	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB