{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T06:32:57Z","timestamp":1788330777996,"version":"build-2803163510"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:p>Personalized PageRank (PPR) is a well-known proximity measure in graphs. To meet the need for dynamic PPR maintenance, recent works have proposed a local update scheme to support incremental computation. Nevertheless, sequential execution of the scheme is still too slow for highspeed stream processing. Therefore, we are motivated to design a parallel approach for dynamic PPR computation. First, as updates always come in batches, we devise a batch processing method to reduce synchronization cost among every single update and enable more parallelism for iterative parallel execution. Our theoretical analysis shows that the parallel approach has the same asymptotic complexity as the sequential approach. Second, we devise novel optimization techniques to effectively reduce runtime overheads for parallel processes. Experimental evaluation shows that our parallel algorithm can achieve orders of magnitude speedups on GPUs and multi-core CPUs compared with the state-of-the-art sequential algorithm.<\/jats:p>","DOI":"10.14778\/3151113.3151121","type":"journal-article","created":{"date-parts":[[2017,10,19]],"date-time":"2017-10-19T12:30:08Z","timestamp":1508416208000},"page":"93-106","source":"Crossref","is-referenced-by-count":44,"title":["Parallel personalized pagerank on dynamic graphs"],"prefix":"10.14778","volume":"11","author":[{"given":"Wentian","family":"Guo","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuchen","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mo","family":"Sha","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kian-Lee","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Extended version. http:\/\/www.comp.nus.edu.sg\/~wentian\/paper\/tr2017--ppr.pdf.  Extended version. http:\/\/www.comp.nus.edu.sg\/~wentian\/paper\/tr2017--ppr.pdf."},{"key":"e_1_2_1_2_1","unstructured":"PAPI. http:\/\/icl.utk.edu\/papi\/.  PAPI. http:\/\/icl.utk.edu\/papi\/."},{"key":"e_1_2_1_3_1","unstructured":"Twitter usage statistics. http:\/\/www.internetlivestats.com\/twitter-statistics\/. accessed 18-April-2017.  Twitter usage statistics. http:\/\/www.internetlivestats.com\/twitter-statistics\/. accessed 18-April-2017."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.46"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777891"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935914"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129116"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522714"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.45"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1086\/229693"},{"key":"e_1_2_1_16_1","first-page":"2","volume-title":"OSDI","volume":"12","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez , Y. Low , H. Gu , D. Bickson , and C. Guestrin . Powergraph: Distributed graph-parallel computation on natural graphs . In OSDI , volume 12 , page 2 , 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI, volume 12, page 2, 2012."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367570"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035920"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600227"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630048"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807594"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983713"},{"key":"e_1_2_1_28_1","volume-title":"Efficient algorithms for personalized pagerank. arXiv preprint arXiv:1512.04633","author":"Lofgren P.","year":"2015","unstructured":"P. Lofgren . Efficient algorithms for personalized pagerank. arXiv preprint arXiv:1512.04633 , 2015 . P. Lofgren. Efficient algorithms for personalized pagerank. arXiv preprint arXiv:1512.04633, 2015."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_2_1_30_1","volume-title":"Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658","author":"Lofgren P.","year":"2013","unstructured":"P. Lofgren and A. Goel . Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658 , 2013 . P. Lofgren and A. Goel. Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658, 2013."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623745"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732978"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.52"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2717511"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.28"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365490.1365500"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783297"},{"key":"e_1_2_1_39_1","volume-title":"The pagerank citation ranking: bringing order to the web","author":"Page L.","year":"1999","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The pagerank citation ranking: bringing order to the web . 1999 . L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: bringing order to the web. 1999."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-014-0179-3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151122"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612692"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994522"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_49_1","volume-title":"Approximate personalized pagerank on dynamic graphs. arXiv preprint arXiv:1603.07796","author":"Zhang H.","year":"2016","unstructured":"H. Zhang , P. Lofgren , and A. Goel . Approximate personalized pagerank on dynamic graphs. arXiv preprint arXiv:1603.07796 , 2016 . H. Zhang, P. Lofgren, and A. Goel. Approximate personalized pagerank on dynamic graphs. arXiv preprint arXiv:1603.07796, 2016."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3151113.3151121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:34:22Z","timestamp":1672223662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3151113.3151121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.14778\/3151113.3151121"],"URL":"https:\/\/doi.org\/10.14778\/3151113.3151121","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,9]]}}}