{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T16:32:58Z","timestamp":1772641978969,"version":"3.50.1"},"reference-count":63,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"unspecified","delay-in-days":19,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title>\n\t  <jats:p>The vertex-centric programming model is now widely used for processing large graphs. User-defined vertex programs are executed in parallel over every vertex of a graph, but the imperative and explicit message-passing style of existing systems makes defining a vertex program unintuitive and difficult. This article presents Fregel, a purely functional domain-specific language for processing large graphs and describes its model, design, and implementation. Fregel is a subset of Haskell, so Haskell tools can be used to test and debug Fregel programs. The vertex-centric computation is abstracted using compositional programming that uses second-order functions on graphs provided by Fregel. A Fregel program can be compiled into imperative programs for use in the Giraph and Pregel+ vertex-centric frameworks. Fregel\u2019s functional nature without side effects enables various transformations and optimizations during the compilation process. Thus, the programmer is freed from the burden of program optimization, which is manually done for existing imperative systems. Experimental results for typical examples demonstrated that the compiled code can be executed with reasonable and promising performance.<\/jats:p>","DOI":"10.1017\/s0956796821000277","type":"journal-article","created":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T13:03:54Z","timestamp":1642683834000},"update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Fregel: a functional domain-specific language for vertex-centric large-scale graph processing"],"prefix":"10.1017","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3708-6624","authenticated-orcid":false,"given":"HIDEYA","family":"IWASAKI","sequence":"first","affiliation":[]},{"given":"KENTO","family":"EMOTO","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2741-5954","authenticated-orcid":false,"given":"AKIMASA","family":"MORIHATA","sequence":"additional","affiliation":[]},{"given":"KIMINORI","family":"MATSUZAKI","sequence":"additional","affiliation":[]},{"given":"ZHENJIANG","family":"HU","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2022,1,20]]},"reference":[{"key":"S0956796821000277_ref30","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983726"},{"key":"S0956796821000277_ref4","unstructured":"Capota, M. , Hegeman, T. , Iosup, A. , Prat-P\u00c9rez, A. , Erling, O. & Boncz, P. A. (2015) Graphalytics: A big data benchmark for graph-processing platforms. In Proceedings of the Third International Workshop on Graph Data Management Experiences and Systems, GRADES 2015, Melbourne, VIC, Australia, May 31\u2013June 4, 2015, pp. 7:1\u20137:6."},{"key":"S0956796821000277_ref40","doi-asserted-by":"publisher","DOI":"10.1145\/2980523.2980529"},{"key":"S0956796821000277_ref45","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610518"},{"key":"S0956796821000277_ref41","first-page":"1673","article-title":"Nscale: Neighborhood-centric analytics on large graphs","volume":"7","author":"Quamar","year":"2014","journal-title":"PVLDB"},{"key":"S0956796821000277_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/2742854.2742884"},{"key":"S0956796821000277_ref57","doi-asserted-by":"publisher","DOI":"10.1561\/1900000056"},{"key":"S0956796821000277_ref62","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2017.63"},{"key":"S0956796821000277_ref36","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"S0956796821000277_ref39","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737953"},{"key":"S0956796821000277_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851153"},{"key":"S0956796821000277_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-019-02821-w"},{"key":"S0956796821000277_ref19","first-page":"950","article-title":"Giraph unchained: Barrierless asynchronous parallel execution in pregel-like graph processing systems","volume":"8","author":"Han","year":"2015","journal-title":"PVLDB"},{"key":"S0956796821000277_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0283-9"},{"key":"S0956796821000277_ref51","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"S0956796821000277_ref52","first-page":"493","article-title":"An experimental comparison of partitioning strategies in distributed graph processing","volume":"10","author":"Verma","year":"2017","journal-title":"PVLDB"},{"key":"S0956796821000277_ref50","first-page":"193","article-title":"From \u201cthink like a vertex\u201d to \u201cthink like a graph\u201d","volume":"7","author":"Tian","year":"2013","journal-title":"PVLDB"},{"key":"S0956796821000277_ref55","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688508"},{"key":"S0956796821000277_ref27","unstructured":"Khan, A. (2017) Vertex-centric graph processing: Good, bad, and the ugly. In Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21\u201324, 2017, pp. 438\u2013441."},{"key":"S0956796821000277_ref38","doi-asserted-by":"publisher","DOI":"10.1145\/2384616.2384644"},{"key":"S0956796821000277_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951938"},{"key":"S0956796821000277_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237792"},{"key":"S0956796821000277_ref42","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0405-2"},{"key":"S0956796821000277_ref11","doi-asserted-by":"crossref","unstructured":"Erwig, M. (1997) Functional programming with graphs. In Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming, ICFP 1997, Peyton Jones, S. L., Tofte, M. & Berman, A. M. (eds). Amsterdam, The Netherlands, June 9\u201311, 1997. ACM, pp. 52\u201365.","DOI":"10.1145\/258949.258955"},{"key":"S0956796821000277_ref20","first-page":"1047","article-title":"An experimental comparison of pregel-like graph processing systems","volume":"7","author":"Han","year":"2014","journal-title":"PVLDB"},{"key":"S0956796821000277_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/1995376.1995394"},{"key":"S0956796821000277_ref32","first-page":"281","article-title":"Large-scale distributed graph computing systems: An experimental evaluation","volume":"8","author":"Lu","year":"2014","journal-title":"PVLDB"},{"key":"S0956796821000277_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500608"},{"key":"S0956796821000277_ref49","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282501"},{"key":"S0956796821000277_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004075"},{"key":"S0956796821000277_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"S0956796821000277_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0305-0"},{"key":"S0956796821000277_ref34","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"S0956796821000277_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/2150976.2151013"},{"key":"S0956796821000277_ref31","first-page":"716","article-title":"Distributed graphlab: A framework for machine learning in the cloud","volume":"5","author":"Low","year":"2012","journal-title":"PVLDB"},{"key":"S0956796821000277_ref18","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-6(3:15)2010"},{"key":"S0956796821000277_ref28","first-page":"1709","article-title":"Systems for big-graphs","volume":"7","author":"Khan","year":"2014","journal-title":"PVLDB"},{"key":"S0956796821000277_ref43","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"S0956796821000277_ref37","doi-asserted-by":"publisher","DOI":"10.1145\/2364527.2364541"},{"key":"S0956796821000277_ref46","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807655"},{"key":"S0956796821000277_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2016.03.006"},{"key":"S0956796821000277_ref56","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2912566"},{"key":"S0956796821000277_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.49"},{"key":"S0956796821000277_ref61","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2518664"},{"key":"S0956796821000277_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807668"},{"key":"S0956796821000277_ref47","first-page":"1906","article-title":"Distributed socialite: A datalog-based language for large-scale graph analysis","volume":"6","author":"Seo","year":"2013","journal-title":"PVLDB"},{"key":"S0956796821000277_ref16","unstructured":"Gonzalez, J. E. , Xin, R. S. , Dave, A. , Crankshaw, D. , Franklin, M. J. & Stoica, I. (2014) Graphx: Graph processing in a distributed dataflow framework. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2014, Broomfield, CO, USA, October 6\u20138, 2014, pp. 599\u2013613."},{"key":"S0956796821000277_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-9459-1"},{"key":"S0956796821000277_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0269-7"},{"key":"S0956796821000277_ref53","unstructured":"Wang, G. , Xie, W. , Demers, A. J. & Gehrke, J. (2013) Asynchronous large-scale graph processing made easy. In Sixth Biennial Conference on Innovative Data Systems Research, CIDR 2013, Asilomar, CA, USA, January 6\u20139, 2013, Online Proceedings."},{"key":"S0956796821000277_ref63","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385961"},{"key":"S0956796821000277_ref15","unstructured":"Gonzalez, J. E. , Low, Y. , Gu, H. , Bickson, D. & Guestrin, C. (2012) Powergraph: Distributed graph-parallel computation on natural graphs. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8\u201310, 2012, pp. 17\u201330."},{"key":"S0956796821000277_ref60","first-page":"1821","article-title":"Pregel algorithms for graph connectivity problems with performance guarantees","volume":"7","author":"Yan","year":"2014","journal-title":"PVLDB"},{"key":"S0956796821000277_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-90686-7_11"},{"key":"S0956796821000277_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192404"},{"key":"S0956796821000277_ref29","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622032"},{"key":"S0956796821000277_ref26","article-title":"Eliminating unnecessary communications in the vertex-centric graph processing by the fregel compiler","volume":"36","author":"Kato","year":"2019","journal-title":"Comput. Software"},{"key":"S0956796821000277_ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09873-9_38"},{"key":"S0956796821000277_ref58","first-page":"1981","article-title":"Blogel: A block-centric framework for distributed computation on real-world graphs","volume":"7","author":"Yan","year":"2014","journal-title":"PVLDB"},{"key":"S0956796821000277_ref59","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741096"},{"key":"S0956796821000277_ref23","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2762294"},{"key":"S0956796821000277_ref44","first-page":"577","article-title":"Optimizing graph algorithms on pregel-like systems","volume":"7","author":"Salihoglu","year":"2014","journal-title":"PVLDB"},{"key":"S0956796821000277_ref54","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796821000277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T03:43:40Z","timestamp":1649389420000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796821000277\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":63,"alternative-id":["S0956796821000277"],"URL":"https:\/\/doi.org\/10.1017\/s0956796821000277","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}],"article-number":"e4"}}