{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T10:22:46Z","timestamp":1770546166666,"version":"3.49.0"},"reference-count":24,"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>\n            Graphs in real life applications are often huge, such as the Web graph and various social networks. These massive graphs are often stored and processed in distributed sites. In this paper, we study graph algorithms that adopt Google's Pregel, an iterative vertex-centric framework for graph processing in the Cloud. We first identify a set of desirable properties of an efficient Pregel algorithm, such as linear space, communication and computation cost per iteration, and logarithmic number of iterations. We define such an algorithm as a\n            <jats:italic>practical Pregel algorithm<\/jats:italic>\n            (PPA). We then propose PPAs for computing\n            <jats:italic>connected components<\/jats:italic>\n            (CCs),\n            <jats:italic>biconnected components<\/jats:italic>\n            (BCCs) and\n            <jats:italic>strongly connected components<\/jats:italic>\n            (SCCs). The PPAs for computing BCCs and SCCs use the PPAs of many fundamental graph problems as building blocks, which are of interest by themselves. Extensive experiments over large real graphs verified the efficiency of our algorithms.\n          <\/jats:p>","DOI":"10.14778\/2733085.2733089","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1821-1832","source":"Crossref","is-referenced-by-count":72,"title":["Pregel algorithms for graph connectivity problems with performance guarantees"],"prefix":"10.14778","volume":"7","author":[{"given":"Da","family":"Yan","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"James","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Kai","family":"Xing","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology"}]},{"given":"Yi","family":"Lu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Wilfred","family":"Ng","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology"}]},{"given":"Yingyi","family":"Bu","sequence":"additional","affiliation":[{"name":"University of California, Irvine"}]}],"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","unstructured":"C. Avery . Giraph : Large-scale graph processing infrastructure on hadoop . Proceedings of the Hadoop Summit. Santa Clara , 2011 . C. Avery. Giraph: Large-scale graph processing infrastructure on hadoop. Proceedings of the Hadoop Summit. Santa Clara, 2011."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.02.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-540-70952-7_22","volume-title":"Formal Methods: Applications and Technology","author":"Barnat J.","year":"2007","unstructured":"J. Barnat and P. Moravec . Parallel algorithms for finding sccs in implicitly given graphs . In Formal Methods: Applications and Technology , pages 316 -- 330 . Springer , 2007 . J. Barnat and P. Moravec. Parallel algorithms for finding sccs in implicitly given graphs. In Formal Methods: Applications and Technology, pages 316--330. Springer, 2007."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213888"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2487985"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/3-540-45591-4_68","volume-title":"Parallel and Distributed Processing","author":"Fleischer L. K.","year":"2000","unstructured":"L. K. Fleischer , B. Hendrickson , and A. Pinar . On identifying strongly connected components in parallel . In Parallel and Distributed Processing , pages 505 -- 511 . Springer , 2000 . L. K. Fleischer, B. Hendrickson, and A. Pinar. On identifying strongly connected components in parallel. In Parallel and Distributed Processing, pages 505--511. Springer, 2000."},{"key":"e_1_2_1_10_1","first-page":"17","volume-title":"OSDI","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 , pages 17 -- 30 , 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI, pages 17--30, 2012."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.254"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732294"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90013-X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463719"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_2_1_22_1","volume-title":"Technical report","author":"Wyllie J. C.","year":"1979","unstructured":"J. C. Wyllie . The complexity of parallel computations. Technical report , Cornell University , 1979 . J. C. Wyllie. The complexity of parallel computations. Technical report, Cornell University, 1979."},{"key":"e_1_2_1_23_1","volume-title":"Blogel: A block-centric framework for distributed computation on real-world graphs. PVLDB, 7(14)","author":"Yan D.","year":"2014","unstructured":"D. Yan , J. Cheng , Y. Lu , and W. Ng . Blogel: A block-centric framework for distributed computation on real-world graphs. PVLDB, 7(14) , 2014 . D. Yan, J. Cheng, Y. Lu, and W. Ng. Blogel: A block-centric framework for distributed computation on real-world graphs. PVLDB, 7(14), 2014."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733089"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2733085.2733089","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:15:35Z","timestamp":1672226135000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2733085.2733089"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":24,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["10.14778\/2733085.2733089"],"URL":"https:\/\/doi.org\/10.14778\/2733085.2733089","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}