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: 10918
Venue: VLDB
Year: 2014
Pagerank: 5.2616887e-05
Overall Rank: 5,946 | 58.64%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,537	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	8.5834428e-05
7,157	The Minimum Wiener Connector Problem	2015	SIGMOD	4.8144713e-05
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3571035e-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
320	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00027577867
486	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022068545
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
768	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.00016919065
1,641	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00011047924
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
2,780	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB	8.1317773e-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
2,210	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.2856573e-05
8,019	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD	4.6041407e-05
1,920	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010090791
6,789	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	4.9251746e-05
4,922	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	5.8233726e-05
7,277	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7794907e-05
8,505	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.4958064e-05
4,791	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9188595e-05
1,641	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00011047924