PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs

Summary: PRSim delivers sublinear-time single-source SimRank queries on large power-law graphs with an index of size O(m). Query cost hinges on reverse PageRank; PRSim outperforms prior work in speed and accuracy with a compact index, and it scales to graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5747
Venue: SIGMOD
Year: 2019
Pagerank: 5.4658632e-05
Overall Rank: 8,212 | 43.66%
DOI: 10.1145/3299869.3319873

Incoming Non-self Citations Over Time

Authors

1. Zhewei Wei (Renmin University of China)
2. Xiaodong He (4Paradigm Inc.)
3. Xiaokui Xiao (National University of Singapore)
4. Sibo Wang (Chinese University of Hong Kong)
5. Yu Liu (Peking University)
6. Xiaoyong Du (Renmin University of China)
7. Ji-Rong Wen (Renmin University of China)

BibTeX Citation

@inproceedings{wei_sigmod19,
        title = {{PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs}},
        author = {Wei, Zhewei and He, Xiaodong and Xiao, Xiaokui and Wang, Sibo and Liu, Yu and Du, Xiaoyong and Wen, Ji-Rong},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319873},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319873},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,892	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	7.0430255e-05
5,826	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	6.074674e-05
6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	5.8763523e-05
8,063	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.4949527e-05
9,314	DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee	2021	VLDB	5.289545e-05
11,383	ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy Guarantee	2023	SIGMOD	5.093636e-05
11,796	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
556	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016564032
653	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00015302705
758	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00014277369
1,365	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011017467
1,588	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.0001026895
2,291	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	8.7973939e-05
3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	6.9974506e-05
4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.9479974e-05
4,216	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	6.8273894e-05
4,825	SLING: A Near-Optimal Index Structure for SimRank	2016	SIGMOD	6.4910166e-05
5,520	Walking in the Cloud: Parallel SimRank at Scale	2016	VLDB	6.1884239e-05
5,741	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	6.1029326e-05
6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	5.8182573e-05
7,153	Towards Maximum Independent Sets on Massive Graphs	2015	VLDB	5.6872221e-05
8,213	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	5.4658632e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
2	3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
3	4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD
4	1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
5	2,291	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB
6	1,365	Scalable Similarity Search for SimRank	2014	SIGMOD
7	9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
8	5,826	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB
9	8,213	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB
10	6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD