Scalable Similarity Search for SimRank

Summary: Scalable SimRank-based similarity search for graphs with billions of edges using a linearized recursive formula and Monte-Carlo estimation of s(u,v). Exploits rapid decay with distance to prune to a local neighborhood and combines two precomputed upper bounds with adaptive sampling to achieve fast top-20 queries after an O(n) preprocess. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h19a13012560233ea
Venue: SIGMOD
Year: 2014
Pagerank: 0.00010771853
Overall Rank: 1,400 | 90.60%
DOI: 10.1145/2588555.2610526

Incoming Non-self Citations Over Time

Authors

1. Mitsuru Kusumoto (Preferred Infrastructure, Inc)
2. Takanori Maehara (Japan Science and Technology Agency; National Institute of Informatics)
3. Ken-ichi Kawarabayashi (Japan Science and Technology Agency; National Institute of Informatics)

BibTeX Citation

@inproceedings{kusumoto_sigmod14,
        title = {{Scalable Similarity Search for SimRank}},
        author = {Kusumoto, Mitsuru and Maehara, Takanori and Kawarabayashi, Ken-ichi},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2610526},
        url = {https://dl.acm.org/doi/10.1145/2588555.2610526},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,103	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0420935e-05
2,346	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	8.599417e-05
4,032	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	6.8373318e-05
4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	6.776232e-05
4,304	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	6.67405e-05
4,942	SLING: A Near-Optimal Index Structure for SimRank	2016	SIGMOD	6.3424951e-05
5,101	Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures	2017	VLDB	6.2712293e-05
5,650	Walking in the Cloud: Parallel SimRank at Scale	2016	VLDB	6.0495936e-05
5,945	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	5.935682e-05
6,584	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	5.7417834e-05
6,757	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	5.6879037e-05
7,991	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	5.4098194e-05
8,384	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.3406945e-05
9,503	DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee	2021	VLDB	5.168414e-05
11,704	ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy Guarantee	2023	SIGMOD	4.9769913e-05
12,104	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB	4.9769913e-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
375	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00019619557
668	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00014978043
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013973978
1,626	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.00010039008
1,866	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.4779341e-05
2,668	Combating Web Spam with TrustRank	2004	VLDB	8.1511061e-05
4,788	LinkClus: Efficient Clustering via Heterogeneous Semantic Links	2006	VLDB	6.4120116e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,346	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB
2	9,636	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
3	7,991	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB
4	1,866	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
5	5,945	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB
6	6,584	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
7	6,757	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
8	8,480	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
9	4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
10	4,304	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB