Please use this identifier to cite or link to this item:
Title: Distributed Algorithms on Exact Personalized PageRank
Authors: Guo, Tao
Cao, Xin
Cong, Gao
Lu, Jiaheng
Lin, Xuemin
Keywords: Personalized PageRank
Random walks
Issue Date: 2017
Source: Guo, T., Cao, X., Cong, G., Lu, J., & Lin, X. (2017). Distributed Algorithms on Exact Personalized PageRank. Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17), 479-494.
Conference: Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17)
Abstract: As one of the most well known graph computation problems, Personalized PageRank is an effective approach for computing the similarity score between two nodes, and it has been widely used in various applications, such as link prediction and recommendation. Due to the high computational cost and space cost of computing the exact Personalized PageRank Vector (PPV), most existing studies compute PPV approximately. In this paper, we propose novel and efficient distributed algorithms that compute PPV exactly based on graph partitioning on a general coordinator-based share-nothing distributed computing platform. Our algorithms takes three aspects into account: the load balance, the communication cost, and the computation cost of each machine. The proposed algorithms only require one time of communication between each machine and the coordinator at query time. The communication cost is bounded, and the work load on each machine is balanced. Comprehensive experiments conducted on five real datasets demonstrate the efficiency and the scalability of our proposed methods.
Description: 16 p.
DOI: 10.1145/3035918.3035920
Schools: School of Computer Science and Engineering 
Interdisciplinary Graduate School (IGS) 
Research Centres: Rapid-Rich Object Search Lab 
Rights: © 2017 Association for Computing Machinery (ACM). This is the author created version of a work that has been peer reviewed and accepted for publication by Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17), Association for Computing Machinery (ACM). It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:IGS Conference Papers
SCSE Conference Papers

Files in This Item:
File Description SizeFormat 
Distributed Algorithms on Exact Personalized PageRank.pdf1.74 MBAdobe PDFThumbnail

Citations 20

Updated on Jul 16, 2024

Web of ScienceTM
Citations 10

Updated on Oct 25, 2023

Page view(s) 20

Updated on Jul 13, 2024

Download(s) 10

Updated on Jul 13, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.