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...
Saved in:
Main Authors: | , , |
---|---|
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 |
id |
sg-smu-ink.sis_research-4902 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-49022018-01-11T06:55:29Z Parallel personalized pagerank on dynamic graphs GUO, Wentian LI, Yuchen LI, Yuchen TAN, Kian-Lee 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. 2017-09-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/3900 info:doi/10.14778/3151113.3151121 https://ink.library.smu.edu.sg/context/sis_research/article/4902/viewcontent/p93_guo.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Graphics and Human Computer Interfaces |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Graphics and Human Computer Interfaces |
spellingShingle |
Graphics and Human Computer Interfaces GUO, Wentian LI, Yuchen LI, Yuchen TAN, Kian-Lee Parallel personalized pagerank on dynamic graphs |
description |
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. |
format |
text |
author |
GUO, Wentian LI, Yuchen LI, Yuchen TAN, Kian-Lee |
author_facet |
GUO, Wentian LI, Yuchen LI, Yuchen TAN, Kian-Lee |
author_sort |
GUO, Wentian |
title |
Parallel personalized pagerank on dynamic graphs |
title_short |
Parallel personalized pagerank on dynamic graphs |
title_full |
Parallel personalized pagerank on dynamic graphs |
title_fullStr |
Parallel personalized pagerank on dynamic graphs |
title_full_unstemmed |
Parallel personalized pagerank on dynamic graphs |
title_sort |
parallel personalized pagerank on dynamic graphs |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2017 |
url |
https://ink.library.smu.edu.sg/sis_research/3900 https://ink.library.smu.edu.sg/context/sis_research/article/4902/viewcontent/p93_guo.pdf |
_version_ |
1770573899757518848 |