SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits

Summary: SimTab provides accuracy-guaranteed top-k and thresholding SimRank queries via tighter confidence bounds from random-walk sampling. Framing as Multi-Armed Bandits with a novel node-sim sampling strategy, it is index-free, scalable to dynamic graphs, and empirically superior. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12110
Venue: VLDB
Year: 2020
Pagerank: 4.1905499e-05
Overall Rank: 11,605 | 19.35%
DOI: 10.14778/3407790.3407819

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,326	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	4.351469e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
753	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00017113124
1,542	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011447877
1,896	More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks	2014	VLDB	0.00010173473
2,875	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB	7.9744337e-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
5,288	SLING: A Near-Optimal Index Structure for SimRank	2016	SIGMOD	5.5799268e-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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,231	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	4.5489304e-05
1,542	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011447877
4,953	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	5.8060034e-05
8,025	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD	4.5988512e-05
4,888	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	5.8494448e-05
4,760	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9342555e-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,232	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	4.5489304e-05
9,326	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	4.351469e-05