Distributed Algorithms on Exact Personalized PageRank
16 p.
Saved in:
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/83007 http://hdl.handle.net/10220/42403 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| id |
sg-ntu-dr.10356-83007 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.10356-830072020-11-01T04:43:30Z Distributed Algorithms on Exact Personalized PageRank Guo, Tao Cao, Xin Cong, Gao Lu, Jiaheng Lin, Xuemin School of Computer Science and Engineering Interdisciplinary Graduate School (IGS) Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17) Rapid-Rich Object Search Lab Personalized PageRank Random walks 16 p. 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. NRF (Natl Research Foundation, S’pore) MOE (Min. of Education, S’pore) Accepted version 2017-05-15T03:46:18Z 2019-12-06T15:10:07Z 2017-05-15T03:46:18Z 2019-12-06T15:10:07Z 2017 Conference Paper 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. https://hdl.handle.net/10356/83007 http://hdl.handle.net/10220/42403 10.1145/3035918.3035920 en © 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]. application/pdf |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
NTU Library |
| collection |
DR-NTU |
| language |
English |
| topic |
Personalized PageRank Random walks |
| spellingShingle |
Personalized PageRank Random walks Guo, Tao Cao, Xin Cong, Gao Lu, Jiaheng Lin, Xuemin Distributed Algorithms on Exact Personalized PageRank |
| description |
16 p. |
| author2 |
School of Computer Science and Engineering |
| author_facet |
School of Computer Science and Engineering Guo, Tao Cao, Xin Cong, Gao Lu, Jiaheng Lin, Xuemin |
| format |
Conference or Workshop Item |
| author |
Guo, Tao Cao, Xin Cong, Gao Lu, Jiaheng Lin, Xuemin |
| author_sort |
Guo, Tao |
| title |
Distributed Algorithms on Exact Personalized PageRank |
| title_short |
Distributed Algorithms on Exact Personalized PageRank |
| title_full |
Distributed Algorithms on Exact Personalized PageRank |
| title_fullStr |
Distributed Algorithms on Exact Personalized PageRank |
| title_full_unstemmed |
Distributed Algorithms on Exact Personalized PageRank |
| title_sort |
distributed algorithms on exact personalized pagerank |
| publishDate |
2017 |
| url |
https://hdl.handle.net/10356/83007 http://hdl.handle.net/10220/42403 |
| _version_ |
1683493690418397184 |