{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:45Z","timestamp":1750694805188,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CF-1703925, IIS-1838154, CCF-2106429, CCF-210718, 2002201"],"award-info":[{"award-number":["CF-1703925, IIS-1838154, CCF-2106429, CCF-210718, 2002201"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585168","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"156-169","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Streaming Euclidean MST to a Constant Factor"],"prefix":"10.1145","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Vincent","family":"Cohen-Addad","sequence":"additional","affiliation":[{"name":"Google Research, Switzerland"}]},{"given":"Rajesh","family":"Jayaram","sequence":"additional","affiliation":[{"name":"Google Research, USA"}]},{"given":"Amit","family":"Levi","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]},{"given":"Erik","family":"Waingarten","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840753"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.25"},{"key":"e_1_3_2_1_4_1","first-page":"343","article-title":"Earth mover distance over high-dimensional spaces","volume":"8","author":"Andoni Alexandr","year":"2008","unstructured":"Alexandr Andoni , Piotr Indyk , and Robert Krauthgamer . 2008 . Earth mover distance over high-dimensional spaces .. In SODA. 8 , 343 \u2013 352 . Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. 2008. Earth mover distance over high-dimensional spaces.. In SODA. 8, 343\u2013352.","journal-title":"SODA."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.82"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039690"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007379"},{"key":"e_1_3_2_1_10_1","volume-title":"Affinity Clustering: Hierarchical Clustering at Scale. In Advances in Neural Information Processing Systems","author":"Bateni Mohammadhossein","year":"2017","unstructured":"Mohammadhossein Bateni , Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , Raimondas Kiveris , Silvio Lattanzi , and Vahab Mirrokni . 2017 . Affinity Clustering: Hierarchical Clustering at Scale. In Advances in Neural Information Processing Systems , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). 30, Curran Associates, Inc. . https:\/\/proceedings.neurips.cc\/paper\/2017\/file\/2e1b24a664f5e9c18f407b2f9c73e821-Paper.pdf Mohammadhossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni. 2017. Affinity Clustering: Hierarchical Clustering at Scale. In Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). 30, Curran Associates, Inc.. https:\/\/proceedings.neurips.cc\/paper\/2017\/file\/2e1b24a664f5e9c18f407b2f9c73e821-Paper.pdf"},{"key":"e_1_3_2_1_11_1","unstructured":"Otakar Boruvka. 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. \t\t\t\t  Otakar Boruvka. 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm."},{"key":"e_1_3_2_1_12_1","volume-title":"International Conference on Machine Learning. 576\u2013585","author":"Braverman Vladimir","year":"2017","unstructured":"Vladimir Braverman , Gereon Frahling , Harry Lang , Christian Sohler , and Lin F Yang . 2017 . Clustering high dimensional dynamic data streams . In International Conference on Machine Learning. 576\u2013585 . Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F Yang. 2017. Clustering high dimensional dynamic data streams. In International Conference on Machine Learning. 576\u2013585."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_23"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar Kevin Chen and Martin Farach-Colton. 2002. Finding frequent items in data streams. Automata languages and programming 784\u2013784. \t\t\t\t  Moses Charikar Kevin Chen and Martin Farach-Colton. 2002. Finding frequent items in data streams. Automata languages and programming 784\u2013784.","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.38"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519979"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Vincent Cohen-Addad Xi Chen Rajesh Jayaram Amit Levi and Erik Waingarten. 2022. Streaming Euclidean MST to a Constant Factor. arXiv preprint arXiv:2212.06546. \t\t\t\t  Vincent Cohen-Addad Xi Chen Rajesh Jayaram Amit Levi and Erik Waingarten. 2022. Streaming Euclidean MST to a Constant Factor. arXiv preprint arXiv:2212.06546.","DOI":"10.1145\/3564246.3585168"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435297"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Artur Czumaj SH Jiang Robert Krauthgamer Pavel Vesel\u1ef3 and Mingwei Yang. 2022. Streaming Facility Location in High Dimension via Geometric Hashing. arXiv preprint arXiv:2204.02095. \t\t\t\t  Artur Czumaj SH Jiang Robert Krauthgamer Pavel Vesel\u1ef3 and Mingwei Yang. 2022. Streaming Facility Location in High Dimension via Geometric Hashing. arXiv preprint arXiv:2204.02095.","DOI":"10.1109\/FOCS54457.2022.00050"},{"key":"e_1_3_2_1_23_1","volume-title":"Robert Krauthgamer, and Pavel Vesel\u1ef3.","author":"Czumaj Artur","year":"2020","unstructured":"Artur Czumaj , Shaofeng H-C Jiang , Robert Krauthgamer, and Pavel Vesel\u1ef3. 2020 . Streaming Algorithms for Geometric Steiner Forest . arXiv preprint arXiv:2011.04324. Artur Czumaj, Shaofeng H-C Jiang, Robert Krauthgamer, and Pavel Vesel\u1ef3. 2020. Streaming Algorithms for Geometric Steiner Forest. arXiv preprint arXiv:2011.04324."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.123"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007386"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/060672121"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"David Eppstein. 2000. Spanning Trees and Spanners.. \t\t\t\t  David Eppstein. 2000. Spanning Trees and Spanners..","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064116"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060622"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250866"},{"key":"e_1_3_2_1_31_1","volume-title":"Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of computing, 8, 1","author":"Har-Peled Sariel","year":"2012","unstructured":"Sariel Har-Peled , Piotr Indyk , and Rajeev Motwani . 2012. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of computing, 8, 1 ( 2012 ), 321\u2013350. Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. 2012. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of computing, 8, 1 (2012), 321\u2013350."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.57"},{"key":"e_1_3_2_1_33_1","unstructured":"Wei Hu Zhao Song Lin F Yang and Peilin Zhong. 2018. Nearly Optimal Dynamic k -Means Clustering for High-Dimensional Data. arXiv preprint arXiv:1802.00459. \t\t\t\t  Wei Hu Zhao Song Lin F Yang and Peilin Zhong. 2018. Nearly Optimal Dynamic k -Means Clustering for High-Dimensional Data. arXiv preprint arXiv:1802.00459."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301366"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_3_2_1_37_1","volume-title":"Workshop on Statistical and Computational Theories of Vision (at ICCV).","author":"Indyk Piotr","year":"2003","unstructured":"Piotr Indyk and Nitin Thaper . 2003 . Fast Color Image Retrieval via Embeddings . In Workshop on Statistical and Computational Theories of Vision (at ICCV). Piotr Indyk and Nitin Thaper. 2003. Fast Color Image Retrieval via Embeddings. In Workshop on Statistical and Computational Theories of Vision (at ICCV)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1229912"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.167"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_55"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578221"},{"volume-title":"Approximation algorithms. 1","author":"Vazirani Vijay V","key":"e_1_3_2_1_44_1","unstructured":"Vijay V Vazirani . 2001. Approximation algorithms. 1 , Springer . Vijay V Vazirani. 2001. Approximation algorithms. 1, Springer."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.2"},{"volume-title":"High-Dimensional Geometric Streaming in Polynomial Space. In 2022 IEEE 63th Annual Symposium on Foundations of Computer Science (FOCS) (FOCS \u201922)","author":"David","key":"e_1_3_2_1_46_1","unstructured":"David P. Woodruff and Taisuke Yasuda. 2022 . High-Dimensional Geometric Streaming in Polynomial Space. In 2022 IEEE 63th Annual Symposium on Foundations of Computer Science (FOCS) (FOCS \u201922) . David P. Woodruff and Taisuke Yasuda. 2022. High-Dimensional Geometric Streaming in Polynomial Space. In 2022 IEEE 63th Annual Symposium on Foundations of Computer Science (FOCS) (FOCS \u201922)."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585168","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585168","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":46,"alternative-id":["10.1145\/3564246.3585168","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585168","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}