{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:27Z","timestamp":1763468247813},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,4]]},"abstract":"<jats:p>We propose FrogWild, a novel algorithm for fast approximation of high PageRank vertices, geared towards reducing network costs of running traditional PageRank algorithms. Our algorithm can be seen as a quantized version of power iteration that performs multiple parallel random walks over a directed graph. One important innovation is that we introduce a modification to the GraphLab framework that only partially synchronizes mirror vertices. This partial synchronization vastly reduces the network traffic generated by traditional PageRank algorithms, thus greatly reducing the per-iteration cost of PageRank. On the other hand, this partial synchronization also creates dependencies between the random walks used to estimate PageRank. Our main theoretical innovation is the analysis of the correlations introduced by this partial synchronization process and a bound establishing that our approximation is close to the true PageRank vector.<\/jats:p>\n          <jats:p>We implement our algorithm in GraphLab and compare it against the default PageRank implementation. We show that our algorithm is very fast, performing each iteration in less than one second on the Twitter graph and can be up to 7x faster compared to the standard GraphLab PageRank implementation.<\/jats:p>","DOI":"10.14778\/2757807.2757812","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"874-885","source":"Crossref","is-referenced-by-count":17,"title":["FrogWild!"],"prefix":"10.14778","volume":"8","author":[{"given":"Ioannis","family":"Mitliagkas","sequence":"first","affiliation":[{"name":"UT Austin"}]},{"given":"Michael","family":"Borokhovich","sequence":"additional","affiliation":[{"name":"UT Austin"}]},{"given":"Alexandros G.","family":"Dimakis","sequence":"additional","affiliation":[{"name":"UT Austin"}]},{"given":"Constantine","family":"Caramanis","sequence":"additional","affiliation":[{"name":"UT Austin"}]}],"member":"320","published-online":{"date-parts":[[2015,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Teradata. http:\/\/www.teradata.com\/Resources\/Videos\/Grow-Loyalty-of-Influential-Customers. Accessed: 2014-11-30.  Teradata. http:\/\/www.teradata.com\/Resources\/Videos\/Grow-Loyalty-of-Influential-Customers. Accessed: 2014-11-30."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273498"},{"key":"e_1_2_1_3_1","volume-title":"http:\/\/aws.amazon.com","year":"2014","unstructured":"Amazon web services. http:\/\/aws.amazon.com , 2014 . Amazon web services. http:\/\/aws.amazon.com, 2014."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777891"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_1_6_1","volume-title":"Monte carlo methods for top-k personalized pagerank lists and name disambiguation. CoRR, abs\/1008.3775","author":"Avrachenkov K.","year":"2010","unstructured":"K. Avrachenkov , N. Litvak , D. Nemirovsky , E. Smirnova , and M. Sokol . Monte carlo methods for top-k personalized pagerank lists and name disambiguation. CoRR, abs\/1008.3775 , 2010 . K. Avrachenkov, N. Litvak, D. Nemirovsky, E. Smirnova, and M. Sokol. Monte carlo methods for top-k personalized pagerank lists and name disambiguation. CoRR, abs\/1008.3775, 2010."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135955"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129098"},{"key":"e_1_2_1_11_1","volume-title":"FrogWild! code repository. https:\/\/github.com\/michaelbor\/frogwild","author":"Borokhovich M.","year":"2014","unstructured":"M. Borokhovich and I. Mitliagkas . FrogWild! code repository. https:\/\/github.com\/michaelbor\/frogwild , 2014 . Accessed : 2014-10-30. M. Borokhovich and I. Mitliagkas. FrogWild! code repository. https:\/\/github.com\/michaelbor\/frogwild, 2014. Accessed: 2014-10-30."},{"key":"e_1_2_1_12_1","volume-title":"Monte Carlo simulation, and queues","author":"Bremaud P.","year":"1999","unstructured":"P. Bremaud . Markov chains: Gibbs fields , Monte Carlo simulation, and queues , volume 31 . springer, 1999 . P. Bremaud. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. springer, 1999."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-006-7146-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432624"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018439"},{"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","volume-title":"ICIS'10","author":"Heidemann J.","year":"2010","unstructured":"J. Heidemann , M. Klier , and F. Probst . Identifying key users in online social networks: A pagerank based approach . In ICIS'10 , 2010 . J. Heidemann, M. Klier, and F. Probst. Identifying key users in online social networks: A pagerank based approach. In ICIS'10, 2010."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_19_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623745"},{"key":"e_1_2_1_21_1","volume-title":"Conference on Uncertainty in Artificial Intelligence (UAI)","author":"Low Y.","year":"2010","unstructured":"Y. Low , J. Gonzalez , A. Kyrola , D. Bickson , C. Guestrin , and J. M. Hellerstein . Graphlab: A new parallel framework for machine learning . In Conference on Uncertainty in Artificial Intelligence (UAI) , July 2010 . Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Graphlab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence (UAI), July 2010."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_23_1","volume-title":"Textrank: Bringing order into texts","author":"Mihalcea R.","year":"2004","unstructured":"R. Mihalcea and P. Tarau . Textrank: Bringing order into texts . Association for Computational Linguistics , 2004 . R. Mihalcea and P. Tarau. Textrank: Bringing order into texts. Association for Computational Linguistics, 2004."},{"key":"e_1_2_1_24_1","volume-title":"FrogWild! -- Long Technical Version","author":"Mitliagkas I.","unstructured":"I. Mitliagkas , M. Borokhovich , A. G. Dimakis , and C. Caramanis . FrogWild! -- Long Technical Version . http:\/\/mitliagkas.github.io\/papers\/FrogWild.pdf, 2015. Accessed: 2015-03-04. I. Mitliagkas, M. Borokhovich, A. G. Dimakis, and C. Caramanis. FrogWild! -- Long Technical Version. http:\/\/mitliagkas.github.io\/papers\/FrogWild.pdf, 2015. Accessed: 2015-03-04."},{"key":"e_1_2_1_25_1","volume-title":"Power laws, pareto distributions and zipf's law. Contemporary physics, 46(5): 323--351","author":"Newman M. E.","year":"2005","unstructured":"M. E. Newman . Power laws, pareto distributions and zipf's law. Contemporary physics, 46(5): 323--351 , 2005 . M. E. Newman. Power laws, pareto distributions and zipf's law. Contemporary physics, 46(5): 323--351, 2005."},{"key":"e_1_2_1_26_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_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41847"},{"key":"e_1_2_1_28_1","first-page":"693","volume-title":"Advances in Neural Information Processing Systems","author":"Recht B.","year":"2011","unstructured":"B. Recht , C. Re , S. Wright , and F. Niu . Hogwild: A lock-free approach to parallelizing stochastic gradient descent . In Advances in Neural Information Processing Systems , pages 693 -- 701 , 2011 . B. Recht, C. Re, S. Wright, and F. Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 693--701, 2011."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970397"},{"key":"e_1_2_1_30_1","unstructured":"N. Satish N. Sundaram M. A. Patwary J. Seo J. Park M. A. Hassaan S. Sengupta Z. Yin and P. Dubey. Navigating the maze of graph analytics frameworks using massive graph datasets.  N. Satish N. Sundaram M. A. Patwary J. Seo J. Park M. A. Hassaan S. Sengupta Z. Yin and P. Dubey. Navigating the maze of graph analytics frameworks using massive graph datasets."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_2_1_32_1","volume-title":"www.virtualbox.org","year":"2014","unstructured":"VirtualBox 4.3. www.virtualbox.org , 2014 . VirtualBox 4.3. www.virtualbox.org, 2014."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2757807.2757812","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:45:21Z","timestamp":1672220721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2757807.2757812"}},"subtitle":["fast PageRank approximations on graph engines"],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":33,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["10.14778\/2757807.2757812"],"URL":"https:\/\/doi.org\/10.14778\/2757807.2757812","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}