{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:55:36Z","timestamp":1771700136447,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>Scaling iterative graph processing applications to large graphs is an important problem. Performance is critical, as data scientists need to execute graph programs many times with varying parameters. The need for a high-level, high-performance programming model has inspired much research on graph programming frameworks.<\/jats:p>\n          <jats:p>In this paper, we show that the important class of computationally light graph applications - applications that perform little computation per vertex - has severe scalability problems across multiple cores as these applications hit an early \"memory wall\" that limits their speedup. We propose a novel block-oriented computation model, in which computation is iterated locally over blocks of highly connected nodes, significantly improving the amount of computation per cache miss. Following this model, we describe the design and implementation of a block-aware graph processing runtime that keeps the familiar vertex-centric programming paradigm while reaping the benefits of block-oriented execution. Our experiments show that block-oriented execution significantly improves the performance of our framework for several graph applications.<\/jats:p>","DOI":"10.14778\/2556549.2556581","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"2014-2025","source":"Crossref","is-referenced-by-count":43,"title":["Fast iterative graph computation with block updates"],"prefix":"10.14778","volume":"6","author":[{"given":"Wenlei","family":"Xie","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guozhang","family":"Wang","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Bindel","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Demers","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Gehrke","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124330"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/323215"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224227"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971538"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223785"},{"key":"e_1_2_1_6_1","volume-title":"Nonlinear Programming","author":"Bertsekas D.","year":"1995","unstructured":"D. Bertsekas. Nonlinear Programming. Athena Scientific, 1995."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080909X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995626"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/264989"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/248979"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387883"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.04.052"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/79567.79570"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/645337.649899"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342004041296"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2010.30"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266273"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1051910"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250759"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387884"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206819"},{"key":"e_1_2_1_25_1","volume-title":"UAI","author":"Low Y.","year":"2010","unstructured":"Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new framework for parallel machine learning. In UAI, 2010."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_28_1","volume-title":"CIDR","author":"McSherry F.","year":"2013","unstructured":"F. McSherry, D. Murray, R. Isaacs, and M. Isard. Differential dataflow. In CIDR, 2013."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-007-0038-9"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/645610.661205"},{"key":"e_1_2_1_31_1","volume-title":"Computer Architecture: A Quantitative Approach. Morgan Kaufmann","author":"Patterson D.","year":"1996","unstructured":"D. Patterson and J. Hennessey. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, second edition, 1996."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_33_1","volume-title":"Fluid Mechanics, Computer Vision, and Materials Science","author":"Sethian J. A.","year":"1999","unstructured":"J. A. Sethian. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, 1999."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/238150"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940281.1940330"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"L. G. Valiant. A bridging model for parallel computation. Commun. ACM 33(8) 1990.","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/16\/1\/071"},{"key":"e_1_2_1_40_1","volume-title":"CIDR","author":"Wang G.","year":"2013","unstructured":"G. Wang, W. Xie, A. Demers, and J. Gehrke. Asynchronous large-scale processing made easy. In CIDR, 2013."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.359"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038929"},{"issue":"4","key":"e_1_2_1_43_1","first-page":"421","article-title":"Parallel implementation of fast sweeping method","volume":"25","author":"Zhao H.","year":"2007","unstructured":"H. Zhao. Parallel implementation of fast sweeping method. Journal of Computational Mathematics, 25(4):421-429, 2007.","journal-title":"Journal of Computational Mathematics"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2556549.2556581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T22:34:45Z","timestamp":1729722885000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2556549.2556581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":43,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2556549.2556581"],"URL":"https:\/\/doi.org\/10.14778\/2556549.2556581","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}