DBScholar

Back to papers

Accuracy Estimate and Optimization Techniques for SimRank Computation

Summary: Develops an accuracy estimator that determines the iterations needed for a target-error SimRank computation. Optimizes iterative cost from O(n⁴) to O(n³) and adds an accuracy-aware threshold-sieving heuristic, validated on Wikipedia. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h562071ed71acf539
Venue
VLDB
Year
2008
Pagerank
0.00014985082
Overall Rank
666 | 95.53%
DOI
10.14778/1453856.1453904

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{lizorkin_vldb08,
        title = {{Accuracy Estimate and Optimization Techniques for SimRank Computation}},
        author = {Lizorkin, Dmitry and Velikhov, Pavel and Grinev, Maxim and Turdakov, Denis},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {422--433},
        doi = {10.14778/1453856.1453904},
        url = {https://doi.org/10.14778/1453856.1453904},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
739 PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks 2011 VLDB 0.00014333298
1,400 Scalable Similarity Search for SimRank 2014 SIGMOD 0.00010776946
1,419 Fast and Exact Top-k Search for Random Walk with Restart 2012 VLDB 0.00010728945
1,626 More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks 2014 VLDB 0.00010043754
1,864 Efficient SimRank-based Similarity Join Over Large Graphs 2013 VLDB 9.4824224e-05
2,345 Efficient Partial-Pairs SimRank Search on Large Networks 2015 VLDB 8.6034897e-05
3,266 Distributed Algorithms on Exact Personalized PageRank 2017 SIGMOD 7.4775e-05
4,031 READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank 2017 VLDB 6.84057e-05
4,150 Efficient Top-K SimRank-based Similarity Join 2015 VLDB 6.7794413e-05
4,303 An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs 2015 VLDB 6.6772109e-05
4,941 SLING: A Near-Optimal Index Structure for SimRank 2016 SIGMOD 6.3454989e-05
5,309 On Link-based Similarity Join 2011 VLDB 6.1865348e-05
5,647 Walking in the Cloud: Parallel SimRank at Scale 2016 VLDB 6.0524588e-05
5,945 Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs 2020 VLDB 5.9384932e-05
6,581 Exact Single-Source SimRank Computation on Large Graphs 2020 SIGMOD 5.7445028e-05
6,752 An Experimental Evaluation of SimRank-based Similarity Search Algorithms 2017 VLDB 5.6905975e-05
7,986 ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs 2018 VLDB 5.4123815e-05
8,379 PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs 2019 SIGMOD 5.3432239e-05
8,471 Efficient Top-K SimRank-based Similarity Join 2014 SIGMOD 5.3350108e-05
9,492 DISK: A Distributed Framework for Single-Source SimRank with Accuracy Guarantee 2021 VLDB 5.1708619e-05
9,628 Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement 2024 VLDB 5.1476979e-05
10,493 PJsim: Towards Precise and Scalable Graph Similarity 2026 SIGMOD 4.9793485e-05
12,098 SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits 2020 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

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
86 XMark: A Benchmark for XML Data Management 2002 VLDB 0.00035810622
2,254 Relational link-based ranking 2004 VLDB 8.7448663e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,400 Scalable Similarity Search for SimRank 2014 SIGMOD
2 5,945 Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs 2020 VLDB
3 8,379 PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs 2019 SIGMOD
4 4,150 Efficient Top-K SimRank-based Similarity Join 2015 VLDB
5 2,345 Efficient Partial-Pairs SimRank Search on Large Networks 2015 VLDB
6 4,031 READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank 2017 VLDB
7 6,581 Exact Single-Source SimRank Computation on Large Graphs 2020 SIGMOD
8 1,626 More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks 2014 VLDB
9 9,628 Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement 2024 VLDB
10 6,752 An Experimental Evaluation of SimRank-based Similarity Search Algorithms 2017 VLDB