Fast and Accurate SimRank Computation via Forward Local Push and Its Parallelization

CategoryPublications 222

Authors: Yue Wang, Yulin Che, Xiang Lian, Lei Chen, Qiong Luo

Published in: IEEE Transactions on Knowledge and Data Engineering(TKDE 2020)

Date of Publication: Feb 28, 2020


Measuring similarity among data objects is important in data analysis and mining. SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the SimRank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing and tracking all-pairs SimRank. Furthermore, we develop an iterative parallel two-step framework for local push to take advantage of modern hardwares with multicore CPUs. We show that our algorithms outperform the state-of-the-art methods.

View Full Text

Keywords2020Incremental computation theoryParallel computation modelsSocial media marketingTKDEYue Wang Previous: Next: