{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:19:53Z","timestamp":1703186393520},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,11]]},"abstract":"<jats:p>Parallel aggregation is a ubiquitous operation in data analytics that is expressed as GROUP BY in SQL, reduce in Hadoop, or segment in TensorFlow. Parallel aggregation starts with an optional local pre-aggregation step and then repartitions the intermediate result across the network. While local pre-aggregation works well for low-cardinality aggregations, the network communication cost remains significant for high-cardinality aggregations even after local pre-aggregation. The problem is that the repartition-based algorithm for high-cardinality aggregation does not fully utilize the network.<\/jats:p>\n          <jats:p>In this work, we first formulate a mathematical model that captures the performance of parallel aggregation. We prove that finding optimal aggregation plans from a known data distribution is NP-hard, assuming the Small Set Expansion conjecture. We propose GRASP, a GReedy Aggregation Scheduling Protocol that decomposes parallel aggregation into phases. GRASP is distribution-aware as it aggregates the most similar partitions in each phase to reduce the transmitted data size in subsequent phases. In addition, GRASP takes the available network bandwidth into account when scheduling aggregations in each phase to maximize network utilization. The experimental evaluation on real data shows that GRASP outperforms repartition-based aggregation by 3.5x and LOOM by 2.0x.<\/jats:p>","DOI":"10.14778\/3291264.3291273","type":"journal-article","created":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T13:13:43Z","timestamp":1549286023000},"page":"292-306","source":"Crossref","is-referenced-by-count":8,"title":["Chasing similarity"],"prefix":"10.14778","volume":"12","author":[{"given":"Feilong","family":"Liu","sequence":"first","affiliation":[{"name":"The Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ario","family":"Salmasi","sequence":"additional","affiliation":[{"name":"The Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Spyros","family":"Blanas","sequence":"additional","affiliation":[{"name":"The Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1402946.1402967"},{"key":"e_1_2_1_2_1","first-page":"13","volume-title":"One-shot Pebbling, and Related Layout Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Austrin P.","year":"2012"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_2_1_4_1","first-page":"376","article-title":"A theorem on trees","volume":"23","author":"Cayley A.","year":"1889","journal-title":"Quarterly Journal of Pure Applied Mathematics"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018448"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325893"},{"key":"e_1_2_1_7_1","first-page":"29","volume-title":"Camdoop: Exploiting In-network Aggregation for Big Data Applications. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012","author":"Costa P.","year":"2012"},{"key":"e_1_2_1_8_1","first-page":"13","volume-title":"Proceedings of the 6th USENIX Conference on Hot Topics in Cloud Computing, HotCloud'14","author":"Culhane W.","year":"2014"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218544"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645918.672512"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732281"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236212"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_1_15_1","unstructured":"GRASP. https:\/\/code.osu.edu\/pythia\/grasp.  GRASP. https:\/\/code.osu.edu\/pythia\/grasp."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/645481.655593"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592576"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/647882.738100"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883037"},{"key":"e_1_2_1_20_1","unstructured":"https:\/\/htor.inf.ethz.ch\/research\/topologies\/.  https:\/\/htor.inf.ethz.ch\/research\/topologies\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079079.3079080"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.878935"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_25_1","volume-title":"Chasing Similarity: Distribution-aware Aggregation Scheduling (Extended Version). CoRR, abs\/1810.00511","author":"Liu F.","year":"2018"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055551"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267840"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060303"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872817"},{"key":"e_1_2_1_30_1","volume-title":"Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks. In 4th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA 2002","author":"Madden S.","year":"2002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674996"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920886"},{"key":"e_1_2_1_33_1","volume-title":"Reproducible Floating-Point Aggregation in RDBMSs. CoRR, abs\/1802.09883","author":"M\u00fcller I.","year":"2018"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747644"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747645"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610521"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536233"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498324"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856319"},{"key":"e_1_2_1_42_1","first-page":"592","volume-title":"Locality-sensitive Operators for Parallel Main-memory Database Clusters. In IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA","author":"R\u00f6diger W.","year":"2014"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260779"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223801"},{"key":"e_1_2_1_46_1","unstructured":"E. Vermote-NASA GSFC and MODAPS SIPS - NASA. (2015). MOD09 MODIS\/Terra L2 Surface Reflectance 5-Min Swath 250m 500m and 1km. NASA LP DAAC.  E. Vermote-NASA GSFC and MODAPS SIPS - NASA. (2015). MOD09 MODIS\/Terra L2 Surface Reflectance 5-Min Swath 250m 500m and 1km. NASA LP DAAC."},{"key":"e_1_2_1_47_1","unstructured":"E. Vermote-NASA GSFC and MODAPS SIPS - NASA. (2015). MOD09A1 MODIS\/Surface Reflectance 8-Day L3 Global 500m SIN Grid. NASA LP DAAC.  E. Vermote-NASA GSFC and MODAPS SIPS - NASA. (2015). MOD09A1 MODIS\/Surface Reflectance 8-Day L3 Global 500m SIN Grid. NASA LP DAAC."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2359675"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.250117"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376720"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015509"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1995441.1995442"},{"key":"e_1_2_1_53_1","unstructured":"https:\/\/www.yelp.com\/dataset\/documentation\/json.  https:\/\/www.yelp.com\/dataset\/documentation\/json."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629600"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723718"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3291264.3291273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:11:26Z","timestamp":1672222286000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3291264.3291273"}},"subtitle":["distribution-aware aggregation scheduling"],"short-title":[],"issued":{"date-parts":[[2018,11]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["10.14778\/3291264.3291273"],"URL":"https:\/\/doi.org\/10.14778\/3291264.3291273","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,11]]}}}