{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:08:53Z","timestamp":1755907733277,"version":"3.44.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>We study the design and analysis of parallel join algorithms in a topology-aware computational model. In this model, the network is modeled as a directed graph, where each edge is associated with a cost function that depends on the data transferred between the two endpoints and the link bandwidth. The computation proceeds in synchronous rounds and the cost of each round is measured as the maximum cost over all the edges in the network. Our main result is an asymptotically optimal join algorithm over symmetric tree topologies. The algorithm generalizes prior topology-aware protocols for set intersection and cartesian product to a binary join over an arbitrary input distribution with possible data skew.<\/jats:p>","DOI":"10.1145\/3651598","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Topology-aware Parallel Joins"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6309-1702","authenticated-orcid":false,"given":"Paraschos","family":"Koutris","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"GYM: A multiround distributed join algorithm. In ICDT.","author":"Afrati Foto N","year":"2017","unstructured":"Foto N Afrati, Manas R Joglekar, Christopher M Re, Semih Salihoglu, and Jeffrey D Ullman. 2017. GYM: A multiround distributed join algorithm. In ICDT."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Pankaj K Agarwal Kyle Fox Kamesh Munagala and Abhinandan Nath. 2016. Parallel algorithms for constructing range and nearest-neighbor searching data structures. In PODS. 429--440.","DOI":"10.1145\/2902251.2902303"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni Aleksandar Nikolov Krzysztof Onak and Grigory Yaroslavtsev. 2014. Parallel algorithms for geometric graph problems. In STOC. 574--583.","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi Xiaorui Sun and Omri Weinstein. 2019. Massively parallel algorithms for finding well-connected components in sparse graphs. In PODC. 461--470.","DOI":"10.1145\/3293611.3331596"},{"volume-title":"A new framework for distributed submodular maximization","author":"da Ponte Barbosa Rafael","key":"e_1_2_1_5_1","unstructured":"Rafael da Ponte Barbosa, Alina Ene, Huy L Nguyen, and Justin Ward. 2016. A new framework for distributed submodular maximization. In FOCS. IEEE, 645--654."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Paul Beame Paraschos Koutris and Dan Suciu. 2013. Communication Steps for Parallel Query Processing. In PODS.","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Paul Beame Paraschos Koutris and Dan Suciu. 2014. Skew in Parallel Query Processing. In PODS.","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_8_1","volume-title":"Andrea Pietracaprina, and Geppino Pucci.","author":"Bilardi Gianfranco","year":"2001","unstructured":"Gianfranco Bilardi, Carlo Fantozzi, Andrea Pietracaprina, and Geppino Pucci. 2001. On the effectiveness of D-BSP as a bridging model of parallel computation. In ICCS. Springer, 579--588."},{"volume-title":"Network-oblivious algorithms","author":"Bilardi Gianfranco","key":"e_1_2_1_9_1","unstructured":"Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci, and Francesco Silvestri. 2007. Network-oblivious algorithms. In IPDPS. IEEE, 1--10."},{"key":"e_1_2_1_10_1","unstructured":"Spyros Blanas Paraschos Koutris and Anastasios Sidiropoulos. 2020. Topology-aware parallel data processing: Models algorithms and systems at scale. In CIDR."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Arkadev Chattopadhyay Michael Langberg Shi Li and Atri Rudra. 2017. Tight network topology dependent bounds on rounds of communication. In SODA. 2524--2539.","DOI":"10.1137\/1.9781611974782.167"},{"volume-title":"Topology matters in communication","author":"Chattopadhyay Arkadev","key":"e_1_2_1_12_1","unstructured":"Arkadev Chattopadhyay, Jaikumar Radhakrishnan, and Atri Rudra. 2014. Topology matters in communication. In FOCS. IEEE, 631--640."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0024723"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari Themis Gouleakis Christian Konrad Slobodan Mitrovi\u0107 and Ronitt Rubinfeld. 2018. Improved massively parallel computation algorithms for mis matching and vertex cover. In PODC. 129--138.","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari and Krzysztof Nowicki. 2020. Massively parallel algorithms for minimum cut. In PODC. 119--128.","DOI":"10.1145\/3382734.3405737"},{"volume-title":"searching, and simulation in the mapreduce framework","author":"Goodrich Michael T","key":"e_1_2_1_17_1","unstructured":"Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, searching, and simulation in the mapreduce framework. In ISAAC. Springer, 374--383."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461554"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Xiao Hu. 2021. Cover or pack: New upper and lower bounds for massively parallel joins. In PODS. 181--198.","DOI":"10.1145\/3452021.3458319"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Xiao Hu Paraschos Koutris and Spyros Blanas. 2021. Algorithms for a Topology-aware Massively Parallel Computation Model. In PODS. ACM 199--214.","DOI":"10.1145\/3452021.3458318"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Xiao Hu and Ke Yi. 2019. Instance and output optimal parallel algorithms for acyclic joins. In PODS. 450--463.","DOI":"10.1145\/3294052.3319698"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3444831.3444833"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Xiao Hu and Ke Yi. 2020b. Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries. In PODS. 411--425.","DOI":"10.1145\/3375395.3387657"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3311967"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Bas Ketsman and Dan Suciu. 2017. A worst-case optimal multi-round algorithm for parallel computation of conjunctive queries. In PODS. ACM 417--428.","DOI":"10.1145\/3034786.3034788"},{"key":"e_1_2_1_26_1","unstructured":"Paraschos Koutris Paul Beame and Dan Suciu. 2016. Worst-case optimal algorithms for parallel query processing. In ICDT."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Paraschos Koutris and Dan Suciu. 2011. Parallel evaluation of conjunctive queries. In PODS. ACM 223--234.","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_1_28_1","volume-title":"Sai Vikneshwar Mani Jayaraman, and Atri Rudra","author":"Langberg Michael","year":"2019","unstructured":"Michael Langberg, Shi Li, Sai Vikneshwar Mani Jayaraman, and Atri Rudra. 2019. Topology dependent bounds for faqs. In PODS. 432--449."},{"key":"e_1_2_1_29_1","series-title":"SIAM Journal on computing","volume-title":"Locality in distributed graph algorithms","author":"Linial Nathan","year":"1992","unstructured":"Nathan Linial. 1992. Locality in distributed graph algorithms. SIAM Journal on computing , Vol. 21, 1 (1992), 193--201."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_32_1","unstructured":"Tao Yufei. 2020. A Simple Parallel Algorithm for Natural Joins on Binary Relations. ICDT."},{"key":"e_1_2_1_33_1","unstructured":"Matei Zaharia Mosharaf Chowdhury Tathagata Das Ankur Dave Justin Ma Murphy McCauly Michael J Franklin Scott Shenker and Ion Stoica. 2012. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. In NSDI. 15--28. io"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651598","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:44Z","timestamp":1755898844000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651598"],"URL":"https:\/\/doi.org\/10.1145\/3651598","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}