Title :
A Space and Time Efficient Algorithm for SimRank Computation
Author :
Yu, Weiren ; Lin, Xuemin ; Le, JiaJin
Author_Institution :
Dept. of Comput. Sci. & Technol., Donghua Univ., Shanghai, China
Abstract :
SimRank has been proposed to rank web documents based on a graph model on hyperlinks. The existing techniques for conducting SimRank computation adopt an iteration computation paradigm. The most efficient technique has the time complexity O(n3) with the space requirement O(n2) in the worst case for each iteration where n is the number of nodes (web documents). In this paper, we propose novel optimization techniques such that each iteration takes the time O(min{n · m,nr}) and requires space O (n + m) where m is the number of edges in a web-graph model and r ≤ log2 7. We also show that our algorithm accelerates the convergence rate of the existing techniques. Moreover, our algorithm not only reduces the time and space complexity of the existing techniques but is also I/O efficient. We conduct extensive experiments on both synthetic and real data sets to demonstrate the efficiency and effectiveness of our iteration techniques.
Keywords :
Internet; computational complexity; document handling; graph theory; iterative methods; SimRank computation; Web documents; Web-graph model; hyperlinks; iteration computation paradigm; optimization techniques; space-time efficient algorithm; time complexity; Acceleration; Algorithm design and analysis; Australia; Clustering algorithms; Computer science; Convergence; Information analysis; Information retrieval; Optimization methods; Space technology; Graph Similarity; Link-based Analysis; Optimal Algorithms; SimRank;
Conference_Titel :
Web Conference (APWEB), 2010 12th International Asia-Pacific
Conference_Location :
Busan
Print_ISBN :
978-1-7695-4012-2
Electronic_ISBN :
978-1-4244-6600-9
DOI :
10.1109/APWeb.2010.42