Ivannikov Institute for System Programming of the RAS

Accuracy Estimate and Optimization Techniques for SimRank Computation.


Lizorkin D., Velikhov P., Grinev M., Turdakov D.


The measure of similarity between objects is a very useful tool in many areas of computer science, including information retrieval. SimRank is a simple and intuitive measure of this kind, based on graph-theoretic model. SimRank is typically computed iteratively, in the spirit of PageRank. However, existing work on SimRank lacks accuracy estimation of iterative computation and has discouraging time complexity.

In this paper we present a technique to estimate the accuracy of computing SimRank iteratively. This technique provides a way to nd out the number of iterations required to achieve a desired accuracy when computing SimRank. We also present optimization techniques that improve the computational complexity of the iterative algorithm from O(n^4) to O(n^3) in the worst case. We also introduce a threshold sieving heuristic and its accuracy estimation that further improves the eciency of the method.

As a practical illustration of our techniques we computed SimRank scores on a subset of English Wikipedia corpus, consisting of the complete set of articles and category links.

Full text of the paper in pdf


In proceedings of Very Large Databases Conference, VLDB, 2008.

Research Group

Information Systems

All publications during 2008 All publications