Accuracy Estimate and Optimization Techniques for SimRank Computation

Summary: Proposes an accuracy-estimation framework for iterative SimRank, enabling early stopping to meet a user-specified error bound. Adds optimization, including a threshold-sieving heuristic, cutting worst-case from O(n^4) to O(n^3) with empirical validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9686
Venue: VLDB
Year: 2008
Pagerank: 0.00017113124
Overall Rank: 753 | 94.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
765	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.0001695147
1,542	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011447877
1,626	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.0001108491
1,896	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.00010173473
2,118	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.5036922e-05
2,875	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	7.9744337e-05
3,853	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	6.6987268e-05
4,760	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9342555e-05
4,888	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	5.8494448e-05
4,953	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	5.8060034e-05
4,992	On Link-based Similarity Join	2011	VLDB	5.7750116e-05
5,288	SLING: A Near-Optimal Index Structure for SimRank	2016	SIGMOD	5.5799268e-05
5,926	Walking in the Cloud: Parallel SimRank at Scale	2016	VLDB	5.2668617e-05
6,149	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	5.1835655e-05
6,823	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	4.9098643e-05
7,593	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	4.6984572e-05
8,025	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD	4.5988512e-05
8,231	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	4.5489304e-05
8,232	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	4.5489304e-05
9,159	DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee	2021	VLDB	4.380727e-05
9,326	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	4.351469e-05
11,605	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
99	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050043993
1,633	Relational link-based ranking	2004	VLDB	0.00011062304

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,542	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011447877
6,149	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	5.1835655e-05
8,231	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	4.5489304e-05
4,953	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	5.8060034e-05
2,875	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	7.9744337e-05
4,888	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	5.8494448e-05
7,593	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	4.6984572e-05
1,896	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.00010173473
9,326	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	4.351469e-05
6,823	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	4.9098643e-05