{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T16:33:04Z","timestamp":1772641984057,"version":"3.50.1"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,12,16]],"date-time":"2018-12-16T00:00:00Z","timestamp":1544918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M025268\/1"],"award-info":[{"award-number":["EP\/M025268\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC","award":["652976"],"award-info":[{"award-number":["652976"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61421003"],"award-info":[{"award-number":["61421003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"The Foundation for Innovative Research Groups of NSFC"},{"DOI":"10.13039\/501100012166","name":"973 Program","doi-asserted-by":"crossref","award":["2014CB340302"],"award-info":[{"award-number":["2014CB340302"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100015639","name":"Beijing Advanced Innovation Center for Big Data and Brain Computing","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015639","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>This article presents GRAPE, a parallel &lt;underline&gt;GRAP&lt;\/underline&gt;h &lt;underline&gt;E&lt;\/underline&gt;ngine for graph computations. GRAPE differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole, without the need for recasting the entire algorithm into a new model. Underlying GRAPE are a simple programming model and a principled approach based on fixpoint computation that starts with partial evaluation and uses an incremental function as the intermediate consequence operator. We show that users can devise existing sequential graph algorithms with minor additions, and GRAPE parallelizes the computation. Under a monotonic condition, the GRAPE parallelization guarantees to converge at correct answers as long as the sequential algorithms are correct. Moreover, we show that algorithms in MapReduce, BSP, and PRAM can be optimally simulated on GRAPE. In addition to the ease of programming, we experimentally verify that GRAPE achieves comparable performance to the state-of-the-art graph systems using real-life and synthetic graphs.<\/jats:p>","DOI":"10.1145\/3282488","type":"journal-article","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T13:17:16Z","timestamp":1545052636000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Parallelizing Sequential Graph Computations"],"prefix":"10.1145","volume":"43","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh, Beihang University, and Shenzhen Institute of Computing Sciences"}]},{"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Jingbo","family":"Xu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Xiaojian","family":"Luo","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Qiang","family":"Yin","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Ping","family":"Lu","sequence":"additional","affiliation":[{"name":"BDBC, Beihang University, Beijing, China"}]},{"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}]},{"given":"Ruiqi","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}]}],"member":"320","published-online":{"date-parts":[[2018,12,16]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2006. UKWeb. http:\/\/law.di.unimi.it\/webdata\/uk-union-2006-06-2007-05\/.  2006. UKWeb. http:\/\/law.di.unimi.it\/webdata\/uk-union-2006-06-2007-05\/."},{"key":"e_1_2_2_2_1","unstructured":"2010. Traffic. http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml.  2010. Traffic. http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml."},{"key":"e_1_2_2_3_1","unstructured":"2011. Movielens. http:\/\/grouplens.org\/datasets\/movielens\/.  2011. Movielens. http:\/\/grouplens.org\/datasets\/movielens\/."},{"key":"e_1_2_2_4_1","unstructured":"2012. Friendster. https:\/\/snap.stanford.edu\/data\/com-Friendster.html.  2012. Friendster. https:\/\/snap.stanford.edu\/data\/com-Friendster.html."},{"key":"e_1_2_2_5_1","unstructured":"2012. MPICH. https:\/\/www.mpich.org\/.  2012. MPICH. https:\/\/www.mpich.org\/."},{"key":"e_1_2_2_6_1","unstructured":"2014. Giraph. http:\/\/giraph.apache.org\/.  2014. Giraph. http:\/\/giraph.apache.org\/."},{"key":"e_1_2_2_7_1","unstructured":"2015. DBpedia. http:\/\/wiki.dbpedia.org\/Datasets.  2015. DBpedia. http:\/\/wiki.dbpedia.org\/Datasets."},{"key":"e_1_2_2_8_1","unstructured":"2017. Apache Hadoop. http:\/\/hadoop.apache.org\/.  2017. Apache Hadoop. http:\/\/hadoop.apache.org\/."},{"key":"e_1_2_2_9_1","unstructured":"2017. GRAPE. http:\/\/grapedb.io\/.  2017. GRAPE. http:\/\/grapedb.io\/."},{"key":"e_1_2_2_10_1","unstructured":"2017. Nethogs. https:\/\/github.com\/raboof\/nethogs.  2017. Nethogs. https:\/\/github.com\/raboof\/nethogs."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_2_13_1","volume-title":"Gutin","author":"Bang-Jensen Jrgen","year":"2008"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/356842.356846"},{"key":"e_1_2_2_15_1","volume-title":"Tsitsiklis","author":"Bertsekas Dimitri P.","year":"1997"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503293"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164147"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2015.2428713"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824056"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196918"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732983"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824048"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035942"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020426"},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the 11th Symposium on Operating Systems Design and Implementation (OSDI'14)","author":"Gonzalez Joseph E.","year":"2014"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/070698920"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732980"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/176979.176984"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95)","author":"Henzinger M. R."},{"key":"e_1_2_2_40_1","volume-title":"Proceedings of the 26th Advances in Neural Information Processing Systems (NIPS'13)","author":"Ho Qirong"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035933"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/243439.243447"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448952"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2011.11.004"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the 15th Workshop on Hot Topics in Operating Systems (HotOS'15)","author":"McSherry Frank","year":"2015"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909166"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541988"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660228"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0046"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815418"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505753"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.95"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_2_64_1","unstructured":"Phil Trinder. 1989. A Functional Database. Ph.D. Dissertation. University of Oxford.   Phil Trinder. 1989. A Functional Database. Ph.D. Dissertation. University of Oxford."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_2_66_1","volume-title":"Handbook of Theoretical Computer Science","author":"Valiant Leslie G."},{"key":"e_1_2_2_67_1","volume-title":"Proceedings of the Sixth Biennial Conference on Innovative Data Systems Research (CIDR'13)","author":"Wang Guozhang","year":"2013"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688508"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2015.2472014"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000056"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741096"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733089"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1991.147605"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749246.2749258"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282488","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3282488","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:29Z","timestamp":1750208249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282488"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,16]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3282488"],"URL":"https:\/\/doi.org\/10.1145\/3282488","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,16]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}