Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
9-2017
Abstract
Personalized PageRank (PPR) is a well-known proximitymeasure in graphs. To meet the need for dynamic PPRmaintenance, recent works have proposed a local updatescheme to support incremental computation. Nevertheless,sequential execution of the scheme is still too slow for highspeedstream processing. Therefore, we are motivated todesign a parallel approach for dynamic PPR computation.First, as updates always come in batches, we devise a batchprocessing method to reduce synchronization cost among everysingle update and enable more parallelism for iterativeparallel execution. Our theoretical analysis shows that theparallel approach has the same asymptotic complexity asthe sequential approach. Second, we devise novel optimizationtechniques to e↵ectively reduce runtime overheads forparallel processes. Experimental evaluation shows that ourparallel algorithm can achieve orders of magnitude speedupson GPUs and multi-core CPUs compared with the state-ofthe-artsequential algorithm.
Discipline
Graphics and Human Computer Interfaces
Publication
Proceedings of the 44th International Conference on Very Large Data Bases, Rio de Janeiro, Brazil, 2017 September 1
Volume
11
Issue
1
First Page
93
Last Page
106
ISBN
2150-8097
Identifier
10.14778/3151113.3151121
City or Country
Rio de Janeiro, Brazil
Citation
GUO, Wentian; LI, Yuchen; LI, Yuchen; and TAN, Kian-Lee.
Parallel personalized pagerank on dynamic graphs. (2017). Proceedings of the 44th International Conference on Very Large Data Bases, Rio de Janeiro, Brazil, 2017 September 1. 11, (1), 93-106.
Available at: https://ink.library.smu.edu.sg/sis_research/3900
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.14778/3151113.3151121