{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T01:59:33Z","timestamp":1787709573599,"version":"build-2784847793"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,10]]},"abstract":"<jats:p>The rapid growth in the volume of many real-world graphs (e.g., social networks, web graphs, and spatial networks) has led to the development of various vertex-centric distributed graph computing systems in recent years. However, real-world graphs from different domains have very different characteristics, which often create bottlenecks in vertex-centric parallel graph computation. We identify three such important characteristics from a wide spectrum of real-world graphs, namely (1)skewed degree distribution, (2)large diameter, and (3)(relatively) high density. Among them, only (1) has been studied by existing systems, but many real-world power-law graphs also exhibit the characteristics of (2) and (3). In this paper, we propose a block-centric framework, called Blogel, which naturally handles all the three adverse graph characteristics. Blogel programmers may think like a block and develop efficient algorithms for various graph problems. We propose parallel algorithms to partition an arbitrary graph into blocks efficiently, and block-centric programs are then run over these blocks. Our experiments on large real-world graphs verified that Blogel is able to achieve orders of magnitude performance improvements over the state-of-the-art distributed graph computing systems.<\/jats:p>","DOI":"10.14778\/2733085.2733103","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1981-1992","source":"Crossref","is-referenced-by-count":184,"title":["Blogel"],"prefix":"10.14778","volume":"7","author":[{"given":"Da","family":"Yan","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Lu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wilfred","family":"Ng","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Hadoop Summit. Santa Clara","author":"Avery C.","year":"2011"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213888"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L"},{"key":"e_1_2_1_4_1","first-page":"17","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2012"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_9_1","volume-title":"Inc.","author":"Kleinberg J.","year":"2005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951406"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556581"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"D. Yan J. Cheng K. Xing Y. Lu W. Ng and Y. Bu. Pregel algorithms for graph connectivity problems with performance guarantees. PVLDB 7(14) 2014.   D. Yan J. Cheng K. Xing Y. Lu W. Ng and Y. Bu. Pregel algorithms for graph connectivity problems with performance guarantees. PVLDB 7(14) 2014.","DOI":"10.14778\/2733085.2733089"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2287036.2287041"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2733085.2733103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:17:28Z","timestamp":1672226248000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2733085.2733103"}},"subtitle":["a block-centric framework for distributed computation on real-world graphs"],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":20,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["10.14778\/2733085.2733103"],"URL":"https:\/\/doi.org\/10.14778\/2733085.2733103","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}