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 | Size | Format | |
---|---|---|---|---|
Distributed Algorithms on Exact Personalized PageRank.pdf | 1.74 MB | Adobe PDF | ![]() View/Open |
SCOPUSTM
Citations
16
Updated on Jan 14, 2021
PublonsTM
Citations
12
Updated on Jan 14, 2021
Page view(s)
257
Updated on Jan 15, 2021
Download(s) 10
280
Updated on Jan 15, 2021
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.