Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/83007
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.
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.
URI: https://hdl.handle.net/10356/83007
http://hdl.handle.net/10220/42403
DOI: 10.1145/3035918.3035920
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: [https://doi.org/10.1145/3035918.3035920].
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
View/Open

SCOPUSTM   
Citations 20

11
checked on Sep 5, 2020

WEB OF SCIENCETM
Citations 50

12
checked on Oct 24, 2020

Page view(s) 50

248
checked on Oct 26, 2020

Download(s) 50

270
checked on Oct 26, 2020

Google ScholarTM

Check

Altmetric


Plumx

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