Parallel personalized pagerank on dynamic graphs

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. T...

Full description

Saved in:
Bibliographic Details
Main Authors: GUO, Wentian, LI, Yuchen, TAN, Kian-Lee
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2017
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/3900
https://ink.library.smu.edu.sg/context/sis_research/article/4902/viewcontent/p93_guo.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.