Exact Single-Source SimRank Computation on Large Graphs

Summary: ExactSim provides the first exact single-source and top-k SimRank on large graphs, surpassing Power Method's infeasibility for graphs with millions of nodes. On real data it yields ground-truth guarantees with high probability and achieves 7-decimal precision within practical query times. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6058
Venue: SIGMOD
Year: 2020
Pagerank: 5.8763523e-05
Overall Rank: 6,446 | 55.78%
DOI: 10.1145/3318464.3389781

Incoming Non-self Citations Over Time

Authors

1. Hanzhi Wang (Renmin University of China)
2. Zhewei Wei (Renmin University of China)
3. Ye Yuan (Beijing Institute of Technology)
4. Xiaoyong Du (Renmin University of China)
5. Ji-Rong Wen (Renmin University of China)

BibTeX Citation

@inproceedings{wang_sigmod20,
        title = {{Exact Single-Source SimRank Computation on Large Graphs}},
        author = {Wang, Hanzhi and Wei, Zhewei and Yuan, Ye and Du, Xiaoyong and Wen, Ji-Rong},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389781},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389781},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,476	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.6090634e-05
9,314	DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee	2021	VLDB	5.289545e-05
10,281	PJsim: Towards Precise and Scalable Graph Similarity	2026	SIGMOD	5.093636e-05
11,383	ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy Guarantee	2023	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.6948178e-05
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,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	6.9319591e-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
8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.4658632e-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	8,303	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
2	3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
3	6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
4	4,216	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
5	1,365	Scalable Similarity Search for SimRank	2014	SIGMOD
6	5,826	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB
7	9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
8	4,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
9	8,213	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB
10	8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD