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.9490698e-05
Overall Rank: 5,914 | 60.24%
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,102	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0463758e-05
6,254	The Minimum Wiener Connector Problem	2015	SIGMOD	5.8337783e-05
8,487	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.3322198e-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
290	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00021955068
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
556	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016500392
739	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.00014333298
1,419	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010728945
1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010201796
2,393	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB	8.5321273e-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	1,798	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD
3	8,471	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
4	1,604	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD
5	6,752	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
6	4,031	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
7	7,075	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD
8	8,662	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	4,303	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
10	1,419	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB