{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:52Z","timestamp":1750219852142,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T00:00:00Z","timestamp":1686960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1740833","CCF-2218678","CCF-2008733"],"award-info":[{"award-number":["CCF-1740833","CCF-2218678","CCF-2008733"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,17]]},"DOI":"10.1145\/3558481.3591096","type":"proceedings-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:22:03Z","timestamp":1685571723000},"page":"77-88","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Massively Parallel Tree Embeddings for High Dimensional Spaces"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3197-2812","authenticated-orcid":false,"given":"AmirMohsen","family":"Ahanchi","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8042-0976","authenticated-orcid":false,"given":"Alexandr","family":"Andoni","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4842-0533","authenticated-orcid":false,"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1498-7519","authenticated-orcid":false,"given":"Marina","family":"Knittel","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1136-9538","authenticated-orcid":false,"given":"Peilin","family":"Zhong","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755586"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"e_1_3_2_1_3_1","volume-title":"West","author":"Alon Noga","year":"1995","unstructured":"Noga Alon, Richard M. Karp, David Peleg, and Douglas B. West. 1995. A Graph- Theoretic Game and Its Application to the k-Server Problem. SIAM J. Comput. (1995), 78--100."},{"volume-title":"Nearest Neighbor Search: the Old, the New, and the Impossible. Ph. D. Dissertation","author":"Andoni Alexandr","key":"e_1_3_2_1_4_1","unstructured":"Alexandr Andoni. 2009. Nearest Neighbor Search: the Old, the New, and the Impossible. Ph. D. Dissertation. Massachusetts Institute of Technology, Cambridge, MA, USA."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_6_1","volume-title":"Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 674--685","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. 2018. Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 674--685."},{"key":"e_1_3_2_1_7_1","first-page":"1","article-title":"Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. In 46th International Colloquium on Automata, Languages, and Programming","volume":"14","author":"Andoni Alexandr","year":"2019","unstructured":"Alexandr Andoni, Clifford Stein, and Peilin Zhong. 2019. Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. In 46th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 14:1--14:16.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384321"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646145"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.98"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310483"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_1_13_1","volume-title":"WAW 2014, Beijing, China, December 17-18, 2014, Proceedings (Lecture Notes in Computer Science","volume":"78","author":"Bahmani Bahman","year":"2014","unstructured":"Bahman Bahmani, Ashish Goel, and Kamesh Munagala. 2014. Efficient Primal- Dual Graph Algorithms for MapReduce. In Algorithms and Models for the Web Graph - 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings (Lecture Notes in Computer Science, Vol. 8882), Anthony Bonato, Fan Chung Graham, and Pawel Pralat (Eds.). Springer, 59--78."},{"key":"e_1_3_2_1_14_1","volume-title":"37th Annual Symposium on Foundations of Computer Science. 184--193","author":"Bartal Yair","year":"1996","unstructured":"Yair Bartal. 1996. Probabilistic Approximations of Metric Spaces and Its Algorith- mic Applications. In 37th Annual Symposium on Foundations of Computer Science. 184--193."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_3_2_1_16_1","volume-title":"Mirrokni","author":"Bateni Mohammad Hossein","year":"2017","unstructured":"Mohammad Hossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, Mohammad-Taghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab S. Mirrokni. 2017. Affinity Clustering: Hierarchical Clustering at Scale. In Advances in Neu- ral Information Processing Systems 30: Annual Conference on Neural Information Processing Systems. 6864--6874."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.162"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_1_19_1","volume-title":"Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms. 15:1--15:14","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. 2019. Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms. 15:1--15:14."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323208"},{"volume-title":"Near-Optimal Massively Parallel Graph Connectivity. In 60th IEEE Annual Symposium on Foundations of Computer Science. 1615--1636","author":"Behnezhad Soheil","key":"e_1_3_2_1_21_1","unstructured":"Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub \u0141acki, and Vahab S. Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. In 60th IEEE Annual Symposium on Foundations of Computer Science. 1615--1636."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424579"},{"volume-title":"Exponentially Faster Massively Parallel Maximal Matching. In 60th IEEE Annual Symposium on Foundations of Computer Science. 1637--1649","author":"Behnezhad Soheil","key":"e_1_3_2_1_23_1","unstructured":"Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. 2019. Exponentially Faster Massively Parallel Maximal Matching. In 60th IEEE Annual Symposium on Foundations of Computer Science. 1637--1649."},{"key":"e_1_3_2_1_24_1","volume-title":"24th ACM Symposium on Parallelism in Algorithms and Architectures. 205--213","author":"Blelloch Guy E.","year":"2012","unstructured":"Guy E. Blelloch, Anupam Gupta, and Kanat Tangwongsan. 2012. Parallel prob- abilistic tree embeddings, k-median, and buy-at-bulk network design. In 24th ACM Symposium on Parallelism in Algorithms and Architectures. 205--213."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806638"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Tsz-Hong Chan Hubert","year":"2005","unstructured":"Hubert Tsz-Hong Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. 2005. On hierarchical routing in doubling metrics. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005. SIAM, 762--771. http:\/\/dl.acm. org\/citation.cfm?id=1070432.1070540"},{"volume-title":"39th Annual Symposium on Foundations of Computer Science. 379--388","author":"Charikar Moses","key":"e_1_3_2_1_27_1","unstructured":"Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge A. Plotkin. 1998. Approximating a Finite Metric by a Small Number of Tree Metrics. In 39th Annual Symposium on Foundations of Computer Science. 379--388."},{"key":"e_1_3_2_1_28_1","unstructured":"Xi Chen Rajesh Jayaram Amit Levi and Erik Waingarten. 2020. An Improved Analysis of the Quadtree for High Dimensional EMD. (2020)."},{"key":"e_1_3_2_1_29_1","article-title":"Round compression for parallel matching algorithms","volume":"49","author":"Czumaj Artur","year":"2019","unstructured":"Artur Czumaj, Jakub \u0141acki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. 2019. Round compression for parallel matching algorithms. SIAM J. Comput. 49, 5 (2019), STOC18--1.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_31_1","volume-title":"Massively Parallel and Dynamic Algorithms for Minimum Size Clustering. CoRR abs\/2106.02685","author":"Epasto Alessandro","year":"2021","unstructured":"Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, and Peilin Zhong. 2021. Massively Parallel and Dynamic Algorithms for Minimum Size Clustering. CoRR abs\/2106.02685 (2021). arXiv:2106.02685 https:\/\/arxiv.org\/abs\/2106.02685"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_3_2_1_33_1","unstructured":"Apache Software Foundation. [n. d.]. Hadoop. https:\/\/hadoop.apache.org\/."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3231591"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","volume":"2210","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 2201--2210."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109665"},{"volume-title":"44th Symposium on Founda- tions of Computer Science (FOCS 2003), 11--14 October 2003, Cambridge, MA, USA, Proceedings. IEEE Computer Society, 534--543","author":"Gupta Anupam","key":"e_1_3_2_1_40_1","unstructured":"Anupam Gupta, Robert Krauthgamer, and James R. Lee. 2003. Bounded Geometries, Fractals, and Low-Distortion Embeddings. In 44th Symposium on Founda- tions of Computer Science (FOCS 2003), 11--14 October 2003, Cambridge, MA, USA, Proceedings. IEEE Computer Society, 534--543."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the 19th International Conference on Autonomous Agents. 1864--1866","author":"Hajiaghayi MohammadTaghi","year":"2020","unstructured":"MohammadTaghi Hajiaghayi and Marina Knittel. 2020. Matching Affinity Clus- tering: Improved Hierarchical Clustering at Scale with Guarantees. In Proceedings of the 19th International Conference on Autonomous Agents. 1864--1866."},{"key":"e_1_3_2_1_43_1","volume-title":"Adaptive Massively Parallel Algorithms for Cut Problems. In SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Kunal Agrawal and I-Ting Angelina Lee (Eds.). ACM, 23--33","author":"Hajiaghayi MohammadTaghi","year":"2022","unstructured":"MohammadTaghi Hajiaghayi, Marina Knittel, Jan Olkowski, and Hamed Saleh. 2022. Adaptive Massively Parallel Algorithms for Cut Problems. In SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Kunal Agrawal and I-Ting Angelina Lee (Eds.). ACM, 23--33."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"MohammadTaghi Hajiaghayi Marina Knittel Hamed Saleh and Hsin-Hao Su. 2022. Adaptive Massively Parallel Constant-Round Tree Contraction. 83:1-- 83:23 pages.","DOI":"10.1145\/3490148.3538576"},{"key":"e_1_3_2_1_45_1","unstructured":"MohammadTaghi Hajiaghayi Hamed Saleh Saeed Seddighin and Xiaorui Sun. 2021. Massively Parallel Algorithms for String Matching with Wildcards. (2021)."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"William Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz maps into a Hilbert space. Contemp. Math. (1984) 189--206.","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 938--948","author":"Karloff Howard","year":"2010","unstructured":"Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A model of com- putation for MapReduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 938--948."},{"key":"e_1_3_2_1_48_1","unstructured":"R. Karp. 1989. A 2k-competitive algorithm for the circle."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Goran Konjevod R. Ravi and F. Sibel Salman. 2001. On approximating planar metrics by tree metrics. Inf. Process. Lett. (2001) 213--219.","DOI":"10.1016\/S0020-0190(01)00161-2"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0473-8"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.60"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009336"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"volume-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms. 1--12","author":"Roughgarden Tim","key":"e_1_3_2_1_54_1","unstructured":"Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. 2016. Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation). In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms. 1--12."},{"key":"e_1_3_2_1_55_1","volume-title":"Hadoop: The definitive guide. \"O'Reilly Media","author":"White Tom","year":"2012","unstructured":"Tom White. 2012. Hadoop: The definitive guide. \"O'Reilly Media, Inc.\"."},{"key":"e_1_3_2_1_56_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning. 5596--5605","author":"Yaroslavtsev Grigory","year":"2018","unstructured":"Grigory Yaroslavtsev and Adithya Vadapalli. 2018. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under \u2113p Distances. In Proceedings of the 35th International Conference on Machine Learning. 5596--5605."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"}],"event":{"name":"SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Orlando FL USA","acronym":"SPAA '23"},"container-title":["Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591096","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591096","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:06Z","timestamp":1750178826000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,17]]},"references-count":57,"alternative-id":["10.1145\/3558481.3591096","10.1145\/3558481"],"URL":"https:\/\/doi.org\/10.1145\/3558481.3591096","relation":{},"subject":[],"published":{"date-parts":[[2023,6,17]]},"assertion":[{"value":"2023-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}