Fast top-k similarity join for SimRank

详细信息    查看全文

• 作者：Ruiqi Li^a ; Xiang Zhao ; ^a ; ^c ; ^{xiangzhao@nudt.edu.cn} ; Haichuan Shang^b ; Yifan Chen^a ; Weidong Xiao^a ; ^c
• 关键词：Top-k ; Similarity join ; Iterative pruning ; Upper bound
• 刊名：Information Sciences
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：381
• 期：Complete
• 页码：1-19
• 全文大小：1510 K
• 卷排序：381

文摘

SimRank is a well-studied similarity measure between two nodes in a network. However, evaluating SimRank of all nodes in a network is not only time-consuming but also not pragmatic, since users are only interested in the most similar pairs in many real-world applications. This paper focuses on top-k similarity join based on SimRank. In this work, we first present an incremental algorithm for computing SimRank. On top of that, we derive an iterative batch pruning framework, which is able to iteratively filter out unpromising nodes and obtain the top-k pairs in a fast mode. Specifically, we define the concept of super node such that for a node in the network, the SimRank with its super node is not less than that with any others. Based on this feature, we propose a tight upper bound for each node that can be easily calculated after each iteration. Experiments on both real-life and synthetic datasets demonstrate that our method achieves better performance and scalability, in comparison with the state-of-the-art solution.