{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T06:01:39Z","timestamp":1768456899835,"version":"3.49.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T00:00:00Z","timestamp":1608163200000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2020,12,17]]},"abstract":"<jats:p>Due to the rapid development of massively parallel data processing systems such as MapReduce and Spark, there have been revived interests in designing algorithms in a massively parallel computational model. Computing multi-way joins, as one of the central algorithmic problems in databases, has received much attention recently. This paper surveys some of the recent algorithms, as well as lower bounds. We focus on multi-round algorithms, while referring readers to [27] for single-round algorithms.<\/jats:p>","DOI":"10.1145\/3444831.3444833","type":"journal-article","created":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T23:52:01Z","timestamp":1608249121000},"page":"6-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Massively Parallel Join Algorithms"],"prefix":"10.1145","volume":"49","author":[{"given":"Xiao","family":"Hu","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"HKUST"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. International Conference on Database Theory","author":"Afrati F.","year":"2017","unstructured":"F. Afrati , M. Joglekar , C. R\u00b4e , S. Salihoglu , and J. D. Ullman . GYM: A multiround join algorithm in MapReduce . In Proc. International Conference on Database Theory , 2017 . F. Afrati, M. Joglekar, C. R\u00b4e, S. Salihoglu, and J. D. Ullman. GYM: A multiround join algorithm in MapReduce. In Proc. International Conference on Database Theory, 2017."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2015836.2015849"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514909"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392412"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365694"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/333115.333120"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_18_1","volume-title":"Cover or pack: New upper and lower bounds for massively parallel joins, https: \/\/users.cs.duke.edu\/~xh102\/cover.pdf. Technical report","author":"Hu X.","year":"2020","unstructured":"X. Hu . Cover or pack: New upper and lower bounds for massively parallel joins, https: \/\/users.cs.duke.edu\/~xh102\/cover.pdf. Technical report , Duke University , 2020 . X. Hu. Cover or pack: New upper and lower bounds for massively parallel joins, https: \/\/users.cs.duke.edu\/~xh102\/cover.pdf. Technical report, Duke University, 2020."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902292"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319698"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387657"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3311967"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902293"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034788"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_26_1","volume-title":"Proc. International Conference on Database Theory","author":"Koutris P.","year":"2016","unstructured":"P. Koutris , P. Beame , and D. Suciu . Worst-case optimal algorithms for parallel query processing . In Proc. International Conference on Database Theory , 2016 . P. Koutris, P. Beame, and D. Suciu. Worst-case optimal algorithms for parallel query processing. In Proc. International Conference on Database Theory, 2016."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3217510"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092931.3092934"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_31_1","volume-title":"23rd International Conference on Database Theory","author":"Tao Y.","year":"2020","unstructured":"Y. Tao . A simple parallel algorithm for natural joins on binary relations . In 23rd International Conference on Database Theory , 2020 . Y. Tao. A simple parallel algorithm for natural joins on binary relations. In 23rd International Conference on Database Theory, 2020."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_33_1","volume-title":"Proc. International Conference on Database Theory","author":"Veldhuizen T.","year":"2014","unstructured":"T. Veldhuizen . Leapfrog triejoin : A simple, worst-case optimal join algorithm . In Proc. International Conference on Database Theory , 2014 . T. Veldhuizen. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory, 2014."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286831.1286840"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3444831.3444833","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3444831.3444833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:13Z","timestamp":1750195693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3444831.3444833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,17]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,12,17]]}},"alternative-id":["10.1145\/3444831.3444833"],"URL":"https:\/\/doi.org\/10.1145\/3444831.3444833","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2020,12,17]]},"assertion":[{"value":"2020-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}