Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement

Summary: Analyzes SimRank similarity-join methods and gives new theoretical results exposing scalability/accuracy gaps. Proposes approximation‑guaranteed threshold/top‑k frameworks and an efficient randomized local‑push all‑pairs algorithm with complexity bounds and strong empirical gains. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13927
Venue: VLDB
Year: 2024
Pagerank: 5.2634238e-05
Overall Rank: 9,471 | 35.03%
DOI: 10.14778/3636218.3636219

Incoming Non-self Citations Over Time

Authors

1. Qian Ge (Peking University)
2. Yu Liu (Beijing Jiaotong University)
3. Yinghao Zhao (Beijing Jiaotong University)
4. Yuetian Sun (Beijing Jiaotong University)
5. Lei Zou (Peking University)
6. Yuxing Chen (Tencent)
7. Anqun Pan (Tencent)

BibTeX Citation

@article{ge_vldb24,
        title = {{Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement}},
        author = {Ge, Qian and Liu, Yu and Zhao, Yinghao and Sun, Yuetian and Zou, Lei and Chen, Yuxing and Pan, Anqun},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {4},
        pages = {617--629},
        doi = {10.14778/3636218.3636219},
        url = {https://doi.org/10.14778/3636218.3636219},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,237	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
653	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00015302705
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,826	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB	6.074674e-05
8,213	ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs	2018	VLDB	5.4658632e-05
11,796	SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits	2020	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
2	1,365	Scalable Similarity Search for SimRank	2014	SIGMOD
3	5,186	On Link-based Similarity Join	2011	VLDB
4	5,826	Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs	2020	VLDB
5	6,634	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB
6	2,291	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB
7	6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD
8	1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
9	8,303	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
10	4,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB