{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T06:33:04Z","timestamp":1788330784287,"version":"build-2803163510"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,23]],"date-time":"2019-10-23T00:00:00Z","timestamp":1571788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CUHK Direct Grant","award":["No.4055114"],"award-info":[{"award-number":["No.4055114"]}]},{"name":"CUHK University Startup Grant","award":["No. 4930911 and No. 5501570"],"award-info":[{"award-number":["No. 4930911 and No. 5501570"]}]},{"name":"CCF-Tencent Open Research Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            Given a graph\n            <jats:italic>G<\/jats:italic>\n            , a source node\n            <jats:italic>s,<\/jats:italic>\n            and a target node\n            <jats:italic>t<\/jats:italic>\n            , the\n            <jats:italic>personalized PageRank<\/jats:italic>\n            (\n            <jats:italic>PPR<\/jats:italic>\n            ) of\n            <jats:italic>t<\/jats:italic>\n            with respect to\n            <jats:italic>s<\/jats:italic>\n            is the probability that a random walk starting from\n            <jats:italic>s<\/jats:italic>\n            terminates at\n            <jats:italic>t<\/jats:italic>\n            . An important variant of the PPR query is\n            <jats:italic>single-source PPR<\/jats:italic>\n            (\n            <jats:italic>SSPPR<\/jats:italic>\n            ), which enumerates all nodes in\n            <jats:italic>G<\/jats:italic>\n            and returns the top-\n            <jats:italic>k<\/jats:italic>\n            nodes with the highest PPR values with respect to a given source\n            <jats:italic>s<\/jats:italic>\n            . PPR in general and SSPPR in particular have important applications in web search and social networks, e.g., in Twitter\u2019s Who-To-Follow recommendation service. However, PPR computation is known to be expensive on large graphs and resistant to indexing. Consequently, previous solutions either use heuristics, which do not guarantee result quality, or rely on the strong computing power of modern data centers, which is costly.\n          <\/jats:p>\n          <jats:p>\n            Motivated by this, we propose effective index-free and index-based algorithms for approximate PPR processing, with rigorous guarantees on result quality. We first present FORA, an approximate SSPPR solution that combines two existing methods\u2014Forward Push (which is fast but does not guarantee quality) and Monte Carlo Random Walk (accurate but slow)\u2014in a simple and yet non-trivial way, leading to both high accuracy and efficiency. Further, FORA includes a simple and effective indexing scheme, as well as a module for top-\n            <jats:italic>k<\/jats:italic>\n            selection with high pruning power. Extensive experiments demonstrate that the proposed solutions are orders of magnitude more efficient than their respective competitors. Notably, on a billion-edge Twitter dataset, FORA answers a top-500 approximate SSPPR query within 1s, using a single commodity server.\n          <\/jats:p>","DOI":"10.1145\/3360902","type":"journal-article","created":{"date-parts":[[2019,10,23]],"date-time":"2019-10-23T15:40:39Z","timestamp":1571845239000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries"],"prefix":"10.1145","volume":"44","author":[{"given":"Sibo","family":"Wang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, N.T., Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renchi","family":"Yang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Runhui","family":"Wang","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenqing","family":"Lin","sequence":"additional","affiliation":[{"name":"Tencent, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"Hamad Bin Khalifa University, Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nan","family":"Tang","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute, HBKU, Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,10,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77004-6_12"},{"key":"e_1_2_1_2_1","volume-title":"Lang","author":"Andersen Reid","year":"2006","unstructured":"Reid Andersen , Fan R. K. Chung , and Kevin J . Lang . 2006 . Local graph partitioning using PageRank vectors. In Proceedings of the FOCS. 475--486. Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. 2006. Local graph partitioning using PageRank vectors. In Proceedings of the FOCS. 475--486."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21286-4_5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935914"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129098"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463717"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the KDD. 15--23","author":"Fujiwara Yasuhiro","year":"2012","unstructured":"Yasuhiro Fujiwara , Makoto Nakatsuji , Takeshi Yamamuro , Hiroaki Shiokawa , and Makoto Onizuka . 2012 . Efficient personalized PageTank with accuracy assurance . In Proceedings of the KDD. 15--23 . Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro, Hiroaki Shiokawa, and Makoto Onizuka. 2012. Efficient personalized PageTank with accuracy assurance. In Proceedings of the KDD. 15--23."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the WWW. 1225--1226","author":"Gupta Manish S.","year":"2008","unstructured":"Manish S. Gupta , Amit Pathak , and Soumen Chakrabarti . 2008 . Fast algorithms for top-k personalized PageRank queries . In Proceedings of the WWW. 1225--1226 . Manish S. Gupta, Amit Pathak, and Soumen Chakrabarti. 2008. Fast algorithms for top-k personalized PageRank queries. In Proceedings of the WWW. 1225--1226."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_2_1_14_1","volume-title":"Topic-sensitive PageRank. In Proceedings of the WWW. 517--526","author":"Haveliwala Taher H.","year":"2002","unstructured":"Taher H. Haveliwala . 2002 . Topic-sensitive PageRank. In Proceedings of the WWW. 517--526 . Taher H. Haveliwala. 2002. Topic-sensitive PageRank. In Proceedings of the WWW. 517--526."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the SIGIR. 41--48","author":"J\u00e4rvelin Kalervo","year":"2000","unstructured":"Kalervo J\u00e4rvelin and Jaana Kek\u00e4l\u00e4inen . 2000 . IR evaluation methods for retrieving highly relevant documents . In Proceedings of the SIGIR. 41--48 . Kalervo J\u00e4rvelin and Jaana Kek\u00e4l\u00e4inen. 2000. IR evaluation methods for retrieving highly relevant documents. In Proceedings of the SIGIR. 41--48."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_17_1","volume-title":"Efficient algorithms for personalized PageRank. Retrieved from: CoRR abs\/1512.04633","author":"Lofgren Peter","year":"2015","unstructured":"Peter Lofgren . 2015. Efficient algorithms for personalized PageRank. Retrieved from: CoRR abs\/1512.04633 ( 2015 ). Peter Lofgren. 2015. Efficient algorithms for personalized PageRank. Retrieved from: CoRR abs\/1512.04633 (2015)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the KDD. 1436--1445","author":"Lofgren Peter A.","unstructured":"Peter A. Lofgren , Siddhartha Banerjee , Ashish Goel , and C. Seshadhri . 2014. FAST-PPR: Scaling personalized PageRank estimation for large graphs . In Proceedings of the KDD. 1436--1445 . Peter A. Lofgren, Siddhartha Banerjee, Ashish Goel, and C. Seshadhri. 2014. FAST-PPR: Scaling personalized PageRank estimation for large graphs. In Proceedings of the KDD. 1436--1445."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732978"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783297"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the ICDCN. 11--26","author":"Sarma Atish Das","year":"2013","unstructured":"Atish Das Sarma , Anisur Rahaman Molla , Gopal Pandurangan , and Eli Upfal . 2013 . Fast distributed PageRank computation . In Proceedings of the ICDCN. 11--26 . Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, and Eli Upfal. 2013. Fast distributed PageRank computation. In Proceedings of the ICDCN. 11--26."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the SIGMOD. 1571--1585","author":"Shin Kijung","unstructured":"Kijung Shin , Jinhong Jung , Lee Sael , and U. Kang . 2015. BEAR: Block elimination approach for random walk with restart on large graphs . In Proceedings of the SIGMOD. 1571--1585 . Kijung Shin, Jinhong Jung, Lee Sael, and U. Kang. 2015. BEAR: Block elimination approach for random walk with restart on large graphs. In Proceedings of the SIGMOD. 1571--1585."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196919"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319873"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196920"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the ICDE.","author":"Yoon Minji","unstructured":"Minji Yoon , Jinhong Jung , and U. Kang . 2018. TPA: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs . In Proceedings of the ICDE. Minji Yoon, Jinhong Jung, and U. Kang. 2018. TPA: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs. In Proceedings of the ICDE."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939804"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536348"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360902","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:37Z","timestamp":1750203877000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,23]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3360902"],"URL":"https:\/\/doi.org\/10.1145\/3360902","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,23]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}