Accuracy estimate and optimization techniques for SimRank computation
Open Access
- 1 August 2008
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 1 (1) , 422-433
Abstract
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 find 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 efficiency 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.Keywords
This publication has 9 references indexed in Scilit:
- PageSim: A Novel Link-Based Similarity Measure for the World Wide Web2006
- Algorithmic Computation and Approximation of Semantic SimilarityWorld Wide Web, 2006
- SimFusion2005
- Scaling link-based similarity search2005
- Scale-Free Networks Are UltrasmallPhysical Review Letters, 2003
- Exploiting hierarchical domain structure to compute similarityACM Transactions on Information Systems, 2003
- SimRank2002
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Co‐citation in the scientific literature: A new measure of the relationship between two documentsJournal of the American Society for Information Science, 1973