Taming Computational Complexity: Efficient and Parallel SimRank Optimizations on Undirected Graphs
File(s)
Accepted version
Author(s)
Yu, W
Lin, X
Le, J
Type
Conference Paper
Abstract
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 SimRank similarity computation on undirected web graphs. We first present a novel algorithm to estimate the SimRank between vertices in O(n3+ Kn2) time, where n is the number of vertices, and K is the number of iterations. In comparison, the most efficient implementation of SimRank algorithm in [1] takes O(K n3 ) time in the worst case. To efficiently handle large-scale computations, 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.
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.
Date Issued
2010-07-15
Date Acceptance
2010-07-15
Citation
11th International Lecture Notes in Computer Science: Conference, WAIM 2010, Jiuzhaigou, China, July 15-17, 2010. Proceedings, 2010, 6184, pp.280-296
ISBN
978-3-642-14246-8
ISSN
0302-9743
Publisher
Springer
Start Page
280
End Page
296
Journal / Book Title
11th International Lecture Notes in Computer Science: Conference, WAIM 2010, Jiuzhaigou, China, July 15-17, 2010. Proceedings
Volume
6184
Copyright Statement
© 2010, Springer-Verlag Berlin Heidelberg. The final publication is available at Springer via https://dx.doi.org/10.1007/978-3-642-14246-8_29
Source
The 11th International Conference on Web-Age Information Management
Publication Status
Published
Start Date
2010-07-15
Coverage Spatial
Sichuan, China