Taming Computational Complexity: Efficient and Parallel SimRank Optimizations on Undirected Graphs
SimRank has been considered as one of the promising link-based ranking algorithms to evaluate similarities of web documents in many modern search engines. In this paper, we investigate the optimization problem of Sim Rank similarity computation on undirected web graphs. We first present a novel algorithm to estimate the SimRank between vertices in O (n3 + K· n2) time, where n is the number of vertices, and K is the number of iterations. In com parison, the most efficient implementation of SimRank algorithm in 1 takes O (K· n3) time in the worst case. To efficiently handle large-scale computa tions, we also propose a parallel implementation of the SimRank algorithm on multiple processors. The experimental evaluations on both synthetic and real-life data sets demonstrate the better computational time and parallel efficiency of our proposed techniques.
Weiren Yu Xuemin Lin Jiajin Le
Donghua University, Shanghai 201620, China University of New South Wales, NSW 2052, Australia University of New South Wales, NSW 2052, Australia Donghua University, Shanghai 201620, China
国际会议
11th International Conference,WAIM 2010(第十一届网络时代管理国际会议)
九寨沟
英文
280-296
2010-07-14（万方平台首次上网日期，不代表论文的发表时间）