{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:14Z","timestamp":1750220234964,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1-4","license":[{"start":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T00:00:00Z","timestamp":1638230400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2021,11,30]]},"abstract":"<jats:p>Aggregation is common in data analytics and crucial to distilling information from large datasets, but current data analytics frameworks do not fully exploit the potential for optimization in such phases. The lack of optimization is particularly notable in current \u201conline\u201d approaches that store data in main memory across nodes, shifting the bottleneck away from disk I\/O toward network and compute resources, thus increasing the relative performance impact of distributed aggregation phases.<\/jats:p>\n          <jats:p>\n            We present ROME, an aggregation system for use within data analytics frameworks or in isolation. ROME uses a set of novel heuristics based primarily on basic knowledge of aggregation functions combined with deployment constraints to efficiently aggregate results from computations performed on individual data subsets across nodes (e.g., merging sorted lists resulting from top-\n            <jats:italic>k<\/jats:italic>\n            ). The user can either provide minimal information that allows our heuristics to be applied directly, or ROME can autodetect the relevant information at little cost. We integrated ROME as a subsystem into the Spark and Flink data analytics frameworks. We use real-world data to experimentally demonstrate speedups up to 3\u00d7 over single-level aggregation overlays, up to 21% over other multi-level overlays, and 50% for iterative algorithms like gradient descent at 100 iterations.\n          <\/jats:p>","DOI":"10.1145\/3516430","type":"journal-article","created":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T20:23:27Z","timestamp":1647462207000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["ROME: All Overlays Lead to Aggregation, but Some Are Faster than Others"],"prefix":"10.1145","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0936-0593","authenticated-orcid":false,"given":"Marcel","family":"Bl\u00f6cher","sequence":"first","affiliation":[{"name":"TU Darmstadt, Darmstadt, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8094-871X","authenticated-orcid":false,"given":"Emilio","family":"Coppa","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-0428","authenticated-orcid":false,"given":"Pascal","family":"Kleber","sequence":"additional","affiliation":[{"name":"TU Darmstadt, Darmstadt, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3864-9078","authenticated-orcid":false,"given":"Patrick","family":"Eugster","sequence":"additional","affiliation":[{"name":"Universit\u00e0 della Svizzera italiana (USI), Switzerland and Purdue University, West Lafayette, IN, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1427-9888","authenticated-orcid":false,"given":"William","family":"Culhane","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8396-3149","authenticated-orcid":false,"given":"Masoud Saeida","family":"Ardekani","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, United States"}]}],"member":"320","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"SIGCOMM","author":"Abu-Libdeh Hussam","year":"2010","unstructured":"Hussam Abu-Libdeh, Paolo Costa, Antony Rowstron, Greg O\u2019Shea, and Austin Donnelly. 2010. Symbiotic routing in future data centers. In SIGCOMM."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0357-y"},{"key":"e_1_3_2_4_2","unstructured":"Apache Software Foundation. 2021. Flink. Retrieved from http:\/\/flink.apache.org."},{"key":"e_1_3_2_5_2","unstructured":"Apache Software Foundation. 2021. Spark. Retrieved from http:\/\/spark.apache.org."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188721"},{"key":"e_1_3_2_7_2","volume-title":"SOCC","author":"Bhatotia Pramod","year":"2011","unstructured":"Pramod Bhatotia, Alexander Wieder, Rodrigo Rodrigues, Umut A. Acar, and Rafael Pasquin. 2011. Incoop: MapReduce for incremental computations. In SOCC."},{"key":"e_1_3_2_8_2","volume-title":"ICDE","author":"Borzsony S.","year":"2001","unstructured":"S. Borzsony, D. Kossmann, and K. Stocker. 2001. The Skyline operator. In ICDE."},{"key":"e_1_3_2_9_2","volume-title":"PODC","author":"Cao P.","year":"2004","unstructured":"P. Cao and Z. Wang. 2004. Efficient Top-K query calculation in distributed networks. In PODC."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2000.832170"},{"key":"e_1_3_2_11_2","volume-title":"MASCOTS","author":"Chen Yanpei","year":"2011","unstructured":"Yanpei Chen, A. Ganapathi, R. Griffith, and R. Katz. 2011. The case for evaluating MapReduce performance using workload suites. In MASCOTS."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/7.106129"},{"key":"e_1_3_2_13_2","first-page":"377","volume-title":"Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Revised Selected Papers","author":"Chuprikov Pavel","year":"2018","unstructured":"Pavel Chuprikov, Alex Davydow, Kirill Kogan, Sergey I. Nikolenko, and Alexander Sirotkin. 2018. Formalizing compute-aggregate problems in cloud computing. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Revised Selected Papers. Springer, 377\u2013391."},{"key":"e_1_3_2_14_2","first-page":"1","volume-title":"ICNP","author":"Chuprikov Pavel","year":"2017","unstructured":"Pavel Chuprikov, Alex Davydow, Kirill Kogan, Sergey I. Nikolenko, and Alexander V. Sirotkin. 2017. Planning in compute-aggregate problems as optimization problems on graphs. In ICNP. 1\u20132."},{"key":"e_1_3_2_15_2","volume-title":"NSDI","author":"Costa Paolo","year":"2012","unstructured":"Paolo Costa, Austin Donnelly, Antony Rowstron, and Greg O\u2019Shea. 2012. Camdoop: Exploiting in-network aggregation for big data applications. In NSDI."},{"key":"e_1_3_2_16_2","volume-title":"Frontiers in Massive Data Analysis","author":"Council National Research","year":"2013","unstructured":"National Research Council et\u00a0al. 2013. Frontiers in Massive Data Analysis. National Academies Press."},{"key":"e_1_3_2_17_2","volume-title":"Optimal \u201cBig Data\u201d Aggregation Systems\u2014From Theory to Practical Application","author":"Culhane W.","year":"2015","unstructured":"W. Culhane. 2015. Optimal \u201cBig Data\u201d Aggregation Systems\u2014From Theory to Practical Application. Ph. D. Dissertation. Purdue University. Retrieved from https:\/\/docs.lib.purdue.edu\/cgi\/viewcontent.cgi?article=1218&context=open_access_dissertations."},{"key":"e_1_3_2_18_2","volume-title":"6th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 14)","author":"Culhane William","year":"2014","unstructured":"William Culhane, Kirill Kogan, Chamikara Jayalath, and Patrick Eugster. 2014. LOOM: Optimal aggregation overlays for in-memory big data processing. In 6th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 14). USENIX Association, Philadelphia, PA."},{"key":"e_1_3_2_19_2","volume-title":"INFOCOM","author":"Culhane William","year":"2015","unstructured":"William Culhane, Kirill Kogan, Chamikara Jayalath, and Patrick Eugster. 2015. Optimal communication structures for big data aggregation. In INFOCOM."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_21_2","first-page":"829\u2013 844","volume-title":"Proceedings of Machine Learning and Systems","volume":"3","author":"Gebara Nadeen","year":"2021","unstructured":"Nadeen Gebara, Manya Ghobadi, and Paolo Costa. 2021. In-network aggregation for shared machine learning clusters. In Proceedings of Machine Learning and Systems, A. Smola, A. Dimakis, and I. Stoica (Eds.), Vol. 3. 829\u2013 844."},{"key":"e_1_3_2_22_2","volume-title":"SOSP","author":"Ghemawat Sanjay","year":"2003","unstructured":"Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 2003. The Google file system. In SOSP."},{"key":"e_1_3_2_23_2","first-page":"1","volume-title":"International Workshop on Communication Optimizations in HPC (COMHPC)","author":"Graham Richard L.","year":"2016","unstructured":"Richard L. Graham, Devendar Bureddy, Pak Lui, Hal Rosenstock, Gilad Shainer, Gil Bloch, Dror Goldenerg, Mike Dubman, Sasha Kotchubievsky, Vladimir Koushnir, et\u00a0al. 2016. Scalable hierarchical aggregation protocol (SHArP): A hardware architecture for efficient data reduction. In International Workshop on Communication Optimizations in HPC (COMHPC). IEEE, 1\u201310."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315480"},{"key":"e_1_3_2_25_2","volume-title":"ATC","author":"Hunt Patrick","year":"2010","unstructured":"Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. 2010. ZooKeeper: Wait-free coordination for internet-scale systems. In ATC."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_3_2_27_2","volume-title":"VLDB","author":"Jain Navendu","year":"2007","unstructured":"Navendu Jain, Dmitry Kit, Prince Mahajan, Praveen Yalagandula, Mike Dahlin, and Yin Zhang. 2007. STAR: Self-tuning aggregation for scalable monitoring. In VLDB."},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/2959100.2959134","volume-title":"RecSys","author":"Juan Yuchin","year":"2016","unstructured":"Yuchin Juan, Yong Zhuang, Wei-Sheng Chin, and Chih-Jen Lin. 2016. Field-aware factorization machines for CTR prediction. In RecSys. ACM, 43\u201350."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2015.7293300"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/7.489505"},{"key":"e_1_3_2_31_2","volume-title":"Fault Tolerance in Optimal Aggregation Overlays for Big Data Applications","author":"Kleber Pascal","year":"2017","unstructured":"Pascal Kleber. 2017. Fault Tolerance in Optimal Aggregation Overlays for Big Data Applications. Master-Thesis. TU Darmstadt."},{"key":"e_1_3_2_32_2","volume-title":"SIGMOD","author":"Kulkarni Sanjeev","year":"2015","unstructured":"Sanjeev Kulkarni, Nikunj Bhagat, Maosong Fu, Vikas Kedigehalli, Christopher Kellogg, Sailesh Mittal, Jignesh M. Patel, Karthik Ramasamy, and Siddarth Taneja. 2015. Twitter Heron: Stream processing at scale. In SIGMOD."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2901318.2901351"},{"key":"e_1_3_2_34_2","first-page":"741","volume-title":"18th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201921)","author":"Lao ChonLam","year":"2021","unstructured":"ChonLam Lao, Yanfang Le, Kshiteej Mahajan, Yixi Chen, Wenfei Wu, Aditya Akella, and Michael Swift. 2021. ATP: In-network aggregation for multi-tenant learning. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201921). USENIX Association, 741\u2013761."},{"key":"e_1_3_2_35_2","volume-title":"Euro-Par","author":"Liu Y.","year":"2011","unstructured":"Y. Liu, Z. Hu, and K. Matsuzaki. 2011. Towards systematic parallel programming over MapReduce. In Euro-Par."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061322"},{"key":"e_1_3_2_37_2","volume-title":"7th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 15)","author":"Mai Luo","year":"2015","unstructured":"Luo Mai, Chuntao Hong, and Paolo Costa. 2015. Optimizing network performance in distributed machine learning. In 7th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 15). USENIX Association, Santa Clara, CA."},{"key":"e_1_3_2_38_2","first-page":"937","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920)","author":"Mai Luo","year":"2020","unstructured":"Luo Mai, Guo Li, Marcel Wagenl\u00e4nder, Konstantinos Fertakis, Andrei-Octavian Brabete, and Peter Pietzuch. 2020. KungFu: Making training in distributed machine learning adaptive. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920). USENIX Association, 937\u2013954."},{"key":"e_1_3_2_39_2","volume-title":"CoNext","author":"Mai Luo","year":"2014","unstructured":"Luo Mai, Lukas Rupprecht, Abdul Alim, Paolo Costa, Matteo Migliavacca, Peter Pietzuch, and Alexander L. Wolf. 2014. NetAgg: Using middleboxes for application-specific on-path aggregation in data centres. In CoNext."},{"key":"e_1_3_2_40_2","volume-title":"POPL","author":"Morihata A.","year":"2009","unstructured":"A. Morihata, K. Matsuzaki, Z. Hu, and M. Takeichi. 2009. The third homomorphism theorem on trees: Downward & upward lead to divide-and-conquer. In POPL."},{"key":"e_1_3_2_41_2","volume-title":"PPoPP","author":"Morozov Dmitriy","year":"2013","unstructured":"Dmitriy Morozov and Gunther Weber. 2013. Distributed merge trees. In PPoPP."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"issue":"4","key":"e_1_3_2_43_2","first-page":"431","article-title":"Big data technologies: A survey","volume":"30","author":"Oussous Ahmed","year":"2018","unstructured":"Ahmed Oussous, Fatima-Zahra Benjelloun, Ayoub Ait Lahcen, and Samir Belfkih. 2018. Big data technologies: A survey. J. King Saud Univ.-Comput. Inf. Sci. 30, 4 (2018), 431\u2013448.","journal-title":"J. King Saud Univ.-Comput. Inf. Sci."},{"key":"e_1_3_2_44_2","first-page":"693","volume-title":"Conference on Advances in Neural Information Processing Systems","author":"Recht Benjamin","year":"2011","unstructured":"Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. 2011. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Conference on Advances in Neural Information Processing Systems. 693\u2013701."},{"key":"e_1_3_2_45_2","volume-title":"ACM HotNets","author":"Sapio Amedeo","year":"2017","unstructured":"Amedeo Sapio, Ibrahim Abdelaziz, Abdulla Aldilaijan, Marco Canini, and Panos Kalnis. 2017. In-network computation is a dumb idea whose time has come. In ACM HotNets."},{"key":"e_1_3_2_46_2","first-page":"785","volume-title":"18th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201921)","author":"Sapio Amedeo","year":"2021","unstructured":"Amedeo Sapio, Marco Canini, Chen-Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan Ports, and Peter Richtarik. 2021. Scaling distributed machine learning with in-network aggregation. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201921). USENIX Association, 785\u2013808."},{"key":"e_1_3_2_47_2","volume-title":"MSST","author":"Shvachko K.","year":"2010","unstructured":"K. Shvachko, Hairong Kuang, S. Radia, and R. Chansler. 2010. The Hadoop distributed file system. In MSST."},{"key":"e_1_3_2_48_2","unstructured":"SIGKDD. 2012. KDD CUP 2012 Data Set. Retrieved from https:\/\/www.csie.ntu.edu.tw\/cjlin\/libsvmtools\/datasets\/binary.html#kdd2012."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959072"},{"key":"e_1_3_2_50_2","unstructured":"The Computational Biology and Functional Genomics Laboratory at DFCI\/Harward. 2015. TGI Database: DNA Sequences. Retrieved from http:\/\/compbio.dfci.harvard.edu\/tgi\/."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389753"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/EDCC.2012.20"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45748-8_27"},{"key":"e_1_3_2_54_2","volume-title":"EuroSys","author":"Venkataraman Shivaram","year":"2013","unstructured":"Shivaram Venkataraman, Erik Bodzsar, Indrajit Roy, Alvin AuYoung, and Robert S. Schreiber. 2013. Presto: Distributed machine learning and graph processing with sparse matrices. In EuroSys."},{"key":"e_1_3_2_55_2","first-page":"172","volume-title":"Proceedings of Machine Learning and Systems","volume":"2","author":"Wang Guanhua","year":"2020","unstructured":"Guanhua Wang, Shivaram Venkataraman, Amar Phanishayee, Nikhil Devanur, Jorgen Thelin, and Ion Stoica. 2020. Blink: Fast and generic collectives for distributed ML. In Proceedings of Machine Learning and Systems, I. Dhillon, D. Papailiopoulos, and V. Sze (Eds.), Vol. 2. 172\u2013186."},{"key":"e_1_3_2_56_2","unstructured":"Wikipedia. 2016. Pageviews Hourly Statistics Dumps. Retrieved from https:\/\/wikitech.wikimedia.org\/wiki\/Analytics\/Data\/Pagecounts-raw."},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2197411"},{"key":"e_1_3_2_58_2","volume-title":"SIGCOMM","author":"Yalagandula Praveen","year":"2004","unstructured":"Praveen Yalagandula and Mike Dahlin. 2004. SDIMS: A scalable distributed information management system. In SIGCOMM."},{"key":"e_1_3_2_59_2","volume-title":"SIGMOD","author":"Yang Hung-chih","year":"2007","unstructured":"Hung-chih Yang, Ali Dasdan, Ruey-Lung Hsiao, and D. Stott Parker. 2007. Map-reduce-merge: Simplified relational data processing on large clusters. In SIGMOD."},{"key":"e_1_3_2_60_2","volume-title":"SOSP","author":"Yu Yuan","year":"2009","unstructured":"Yuan Yu, Pradeep Kumar Gunda, and Michael Isard. 2009. Distributed aggregation for data-parallel computing: Interfaces and implementations. In SOSP."},{"key":"e_1_3_2_61_2","volume-title":"NSDI","author":"Zaharia M.","year":"2012","unstructured":"M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica. 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In NSDI."},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.122211.00017"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3516430","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3516430","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:21Z","timestamp":1750188621000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3516430"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,30]]},"references-count":61,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2021,11,30]]}},"alternative-id":["10.1145\/3516430"],"URL":"https:\/\/doi.org\/10.1145\/3516430","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"type":"print","value":"0734-2071"},{"type":"electronic","value":"1557-7333"}],"subject":[],"published":{"date-parts":[[2021,11,30]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}