{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T19:55:16Z","timestamp":1759694116353},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>As Personalized PageRank has been widely leveraged for ranking on a graph, the efficient computation of Personalized PageRank Vector (PPV) becomes a prominent issue. In this paper, we propose FastPPV, an approximate PPV computation algorithm that is incremental and accuracy-aware. Our approach hinges on a novel paradigm of scheduled approximation: the computation is partitioned and scheduled for processing in an \"organized\" way, such that we can gradually improve our PPV estimation in an incremental manner, and quantify the accuracy of our approximation at query time. Guided by this principle, we develop an efficient hub based realization, where we adopt the metric of hub-length to partition and schedule random walk tours so that the approximation error reduces exponentially over iterations. Furthermore, as tours are segmented by hubs, the shared substructures between different tours (around the same hub) can be reused to speed up query processing both within and across iterations. Finally, we evaluate FastPPV over two real-world graphs, and show that it not only significantly outperforms two state-of-the-art baselines in both online and offline phrases, but also scale well on larger graphs. In particular, we are able to achieve near-constant time online query processing irrespective of graph size.<\/jats:p>","DOI":"10.14778\/2536336.2536348","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"481-492","source":"Crossref","is-referenced-by-count":29,"title":["Incremental and accuracy-aware personalized pagerank through scheduled approximation"],"prefix":"10.14778","volume":"6","author":[{"given":"Fanwei","family":"Zhu","sequence":"first","affiliation":[{"name":"Zhejiang University City College, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Fang","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign and Advanced Digital Sciences Center, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin Chen-Chuan","family":"Chang","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign and Advanced Digital Sciences Center, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Ying","sequence":"additional","affiliation":[{"name":"Zhejiang University City College, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"475","volume-title":"FOCS","author":"Andersen R.","year":"2006","unstructured":"R. Andersen , F. Chung , and K. Lang . Local graph partitioning using pagerank vectors . In FOCS , pages 475 - 486 , 2006 . R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. In FOCS, pages 475-486, 2006."},{"key":"e_1_2_1_2_1","first-page":"973","volume-title":"SIGMOD","author":"Bahmani B.","year":"2011","unstructured":"B. Bahmani , K. Chakrabarti , and D. Xin . Fast personalized PageRank on MapReduce . In SIGMOD , pages 973 - 984 , 2011 . B. Bahmani, K. Chakrabarti, and D. Xin. Fast personalized PageRank on MapReduce. In SIGMOD, pages 973-984, 2011."},{"key":"e_1_2_1_3_1","first-page":"173","volume-title":"VLDB","author":"Bahmani B.","year":"2010","unstructured":"B. Bahmani , A. Chowdhury , and A. Goel . Fast incremental and personalized PageRank . VLDB , pages 173 - 184 , 2010 . B. Bahmani, A. Chowdhury, and A. Goel. Fast incremental and personalized PageRank. VLDB, pages 173-184, 2010."},{"key":"e_1_2_1_4_1","first-page":"564","volume-title":"VLDB","author":"Balmin A.","year":"2004","unstructured":"A. Balmin , V. Hristidis , and Y. Papakonstantinou . ObjectRank: Authority-based keyword search in databases . In VLDB , pages 564 - 575 , 2004 . A. Balmin, V. Hristidis, and Y. Papakonstantinou. ObjectRank: Authority-based keyword search in databases. In VLDB, pages 564-575, 2004."},{"issue":"1","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1080\/15427951.2006.10129116","article-title":"Bookmark-coloring algorithm for personalized pagerank computing","volume":"3","author":"Berkhin P.","year":"2006","unstructured":"P. Berkhin . Bookmark-coloring algorithm for personalized pagerank computing . Internet Mathematics , 3 ( 1 ): 41 - 62 , 2006 . P. Berkhin. Bookmark-coloring algorithm for personalized pagerank computing. Internet Mathematics, 3(1):41-62, 2006.","journal-title":"Internet Mathematics"},{"key":"e_1_2_1_6_1","first-page":"571","volume-title":"WWW","author":"Chakrabarti S.","year":"2007","unstructured":"S. Chakrabarti . Dynamic personalized pagerank in entity-relation graphs . In WWW , pages 571 - 580 , 2007 . S. Chakrabarti. Dynamic personalized pagerank in entity-relation graphs. In WWW, pages 571-580, 2007."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/s00778-010-0204-8","article-title":"Index design and query processing for graph conductance search","volume":"20","author":"Chakrabarti S.","year":"2010","unstructured":"S. Chakrabarti , A. Pathak , and M. Gupta . Index design and query processing for graph conductance search . VLDBJ , 20 : 445 - 470 , 2010 . S. Chakrabarti, A. Pathak, and M. Gupta. Index design and query processing for graph conductance search. VLDBJ, 20:445-470, 2010.","journal-title":"VLDBJ"},{"issue":"3","key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1080\/15427951.2005.10129104","article-title":"Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments","volume":"2","author":"Fogaras D.","year":"2005","unstructured":"D. Fogaras , B. R\u00e1cz , K. Csalog\u00e1ny , and T. Sarl\u00f3s . Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments . Internet Mathematics , 2 ( 3 ): 333 - 358 , 2005 . D. Fogaras, B. R\u00e1cz, K. Csalog\u00e1ny, and T. Sarl\u00f3s. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3):333-358, 2005.","journal-title":"Internet Mathematics"},{"key":"e_1_2_1_9_1","first-page":"15","volume-title":"SIGKDD","author":"Fujiwara Y.","year":"2012","unstructured":"Y. Fujiwara , M. Nakatsuji , T. Yamamuro , H. Shiokawa , and M. Onizuka . Efficient personalized pagerank with accuracy assurance . In SIGKDD , pages 15 - 23 , 2012 . Y. Fujiwara, M. Nakatsuji, T. Yamamuro, H. Shiokawa, and M. Onizuka. Efficient personalized pagerank with accuracy assurance. In SIGKDD, pages 15-23, 2012."},{"key":"e_1_2_1_10_1","first-page":"1225","volume-title":"WWW","author":"Gupta M.","year":"2008","unstructured":"M. Gupta , A. Pathak , and S. Chakrabarti . Fast algorithms for top-k personalized pagerank queries . In WWW , pages 1225 - 1226 , 2008 . M. Gupta, A. Pathak, and S. Chakrabarti. Fast algorithms for top-k personalized pagerank queries. In WWW, pages 1225-1226, 2008."},{"issue":"4","key":"e_1_2_1_11_1","first-page":"784","article-title":"a Context-Sensitive ranking algorithm for web search","volume":"15","author":"Haveliwala T. H.","year":"2003","unstructured":"T. H. Haveliwala . Topic-Sensitive PageRank : a Context-Sensitive ranking algorithm for web search . TKDE , 15 ( 4 ): 784 - 796 , 2003 . T. H. Haveliwala. Topic-Sensitive PageRank: a Context-Sensitive ranking algorithm for web search. TKDE, 15(4):784-796, 2003.","journal-title":"TKDE"},{"key":"e_1_2_1_12_1","first-page":"271","volume-title":"WWW","author":"Jeh G.","year":"2003","unstructured":"G. Jeh and J. Widom . Scaling personalized web search . In WWW , pages 271 - 279 , 2003 . G. Jeh and J. Widom. Scaling personalized web search. In WWW, pages 271-279, 2003."},{"key":"e_1_2_1_13_1","volume-title":"Exploiting the block structure of the web for computing PageRank. Technical report","author":"Kamvar S.","year":"2003","unstructured":"S. Kamvar , T. Haveliwala , C. Manning , and G. Golub . Exploiting the block structure of the web for computing PageRank. Technical report , Stanford University , 2003 . S. Kamvar, T. Haveliwala, C. Manning, and G. Golub. Exploiting the block structure of the web for computing PageRank. Technical report, Stanford University, 2003."},{"key":"e_1_2_1_14_1","volume-title":"The PageRank citation ranking: Bringing order to the web. Technical report","author":"Page L.","year":"1999","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The PageRank citation ranking: Bringing order to the web. Technical report , Stanford University , 1999 . L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford University, 1999."},{"key":"e_1_2_1_15_1","volume-title":"Probability, random variables, and stochastic processes","author":"Papoulis A.","year":"1965","unstructured":"A. Papoulis , S. Pillai , and S. Unnikrishna . Probability, random variables, and stochastic processes . McGraw-hill New York , 1965 . A. Papoulis, S. Pillai, and S. Unnikrishna. Probability, random variables, and stochastic processes. McGraw-hill New York, 1965."},{"key":"e_1_2_1_16_1","first-page":"1489","volume-title":"ICDE","author":"Pathak A.","year":"2008","unstructured":"A. Pathak , S. Chakrabarti , and M. Gupta . Index design for dynamic personalized PageRank . In ICDE , pages 1489 - 1491 , 2008 . A. Pathak, S. Chakrabarti, and M. Gupta. Index design for dynamic personalized PageRank. In ICDE, pages 1489-1491, 2008."},{"key":"e_1_2_1_17_1","first-page":"1441","volume-title":"NIPS","author":"Richardson M.","year":"2002","unstructured":"M. Richardson and P. Domingos . The intelligent surfer: Probabilistic combination of link and content information in pagerank . In NIPS , pages 1441 - 1448 , 2002 . M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in pagerank. In NIPS, pages 1441-1448, 2002."},{"key":"e_1_2_1_18_1","first-page":"513","volume-title":"SIGKDD","author":"Sarkar P.","year":"2010","unstructured":"P. Sarkar and A. Moore . Fast nearest-neighbor search in disk-resident graphs . In SIGKDD , pages 513 - 522 , 2010 . P. Sarkar and A. Moore. Fast nearest-neighbor search in disk-resident graphs. In SIGKDD, pages 513-522, 2010."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536336.2536348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:43:31Z","timestamp":1672224211000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536336.2536348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.14778\/2536336.2536348"],"URL":"https:\/\/doi.org\/10.14778\/2536336.2536348","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,4]]}}}