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: 11106
Venue: VLDB
Year: 2014
Pagerank: 6.0777346e-05
Overall Rank: 5,815 | 60.11%
DOI: 10.14778/2732269.2732276

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,073	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.2209912e-05
6,125	The Minimum Wiener Connector Problem	2015	SIGMOD	5.9675732e-05
9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.282937e-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
285	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00022365284
546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016734556
556	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016564032
731	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.00014537965
1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010848387
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134
2,362	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB	8.6889619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,149	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB
2	1,769	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD
3	8,303	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
4	1,628	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD
5	6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
6	3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
7	6,940	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD
8	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	4,216	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
10	1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB