Reverse Top-k Search using Random Walk with Restart

Summary: Reverse top-k proximity search using random walk with restart (RWR) for large, heterogeneous graphs. An indexing-based online algorithm dramatically reduces computation and storage compared to naïve RWR, enabling scalable reverse top-k queries on big graph datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha8e9ea8e56e2ffb0
Venue: VLDB
Year: 2014
Pagerank: 5.9281079e-05
Overall Rank: 5,928 | 60.27%
DOI: 10.14778/2732269.2732276
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Adams Wei Yu (Carnegie Mellon University; University of Hong Kong)
2. Nikos Mamoulis (University of Hong Kong)
3. Hao Su (Stanford University)

BibTeX Citation

@article{yu_vldb14,
        title = {{Reverse Top-k Search using Random Walk with Restart}},
        author = {Yu, Adams Wei and Mamoulis, Nikos and Su, Hao},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {5},
        pages = {401--412},
        doi = {10.14778/2732269.2732276},
        url = {https://doi.org/10.14778/2732269.2732276},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,103	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0280807e-05
6,254	The Minimum Wiener Connector Problem	2015	SIGMOD	5.8165397e-05
8,382	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.3266895e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
292	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00021888861
547	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016545689
555	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016476141
741	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.00014302
1,407	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010736384
1,574	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010164216
2,382	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB	8.5296758e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,861	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB
2	1,796	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD
3	8,495	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
4	1,602	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD
5	6,776	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
6	4,052	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
7	7,031	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD
8	8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	4,320	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
10	1,407	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB