{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T17:17:05Z","timestamp":1756574225864,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519979","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"222-233","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["New streaming algorithms for high dimensional EMD and MST"],"prefix":"10.1145","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"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":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"volume-title":"Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC \u20192014)","author":"Agarwal Pankaj K.","unstructured":"Pankaj K. Agarwal and R. Sharathkumar . 2014. Approximation algorithms for bipartite matching with metric and geometric costs . In Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC \u20192014) . 555\u2013564. Pankaj K. Agarwal and R. Sharathkumar. 2014. Approximation algorithms for bipartite matching with metric and geometric costs. In Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC \u20192014). 555\u2013564.","key":"e_1_3_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.5555\/1747597.1748049"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192008)","author":"Andoni Alexandr","year":"2008","unstructured":"Alexandr Andoni , Piotr Indyk , and Robert Krauthgamer . 2008 . Earth mover distance over high-dimensional spaces . In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192008) . 343\u2013352. Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. 2008. Earth mover distance over high-dimensional spaces. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192008). 343\u2013352."},{"doi-asserted-by":"crossref","unstructured":"Alexandr Andoni Robert Krauthgamer and Krzysztof Onak. 2010. Streaming algorithms from precision sampling. arXiv preprint arXiv:1011.1263.  Alexandr Andoni Robert Krauthgamer and Krzysztof Onak. 2010. Streaming algorithms from precision sampling. arXiv preprint arXiv:1011.1263.","key":"e_1_3_2_1_4_1","DOI":"10.1109\/FOCS.2011.82"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1145\/2746539.2746552"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1145\/2591796.2591805"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.5555\/3305381.3305404"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.5555\/3524938.3524985"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems 30 (NeurIPS \u20192017)","author":"Bateni MohammadHossein","year":"2017","unstructured":"MohammadHossein Bateni , Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , Raimondas Kiveris , Solvio Lattanzi , and Vahab Mirrokni . 2017 . Affinity Clustering: Hierarchical Clustering at Scale . In Proceedings of Advances in Neural Information Processing Systems 30 (NeurIPS \u20192017) . MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Solvio Lattanzi, and Vahab Mirrokni. 2017. Affinity Clustering: Hierarchical Clustering at Scale. In Proceedings of Advances in Neural Information Processing Systems 30 (NeurIPS \u20192017)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/2582112.2582120"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/2024156.2024192"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1145\/509907.509965"},{"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.  Moses Charikar Kevin Chen and Martin Farach-Colton. 2002. Finding frequent items in data streams. Automata languages and programming 784\u2013784.","key":"e_1_3_2_1_14_1","DOI":"10.1007\/3-540-45465-9_59"},{"doi-asserted-by":"crossref","unstructured":"Xi Chen Rajesh Jayaram Amit Levi and Erik Waingarten. 2021. New Streaming Algorithms for High Dimensional EMD and MST. arXiv: 2111.03528.  Xi Chen Rajesh Jayaram Amit Levi and Erik Waingarten. 2021. New Streaming Algorithms for High Dimensional EMD and MST. arXiv: 2111.03528.","key":"e_1_3_2_1_15_1","DOI":"10.1145\/3519935.3519979"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1007\/s10994-018-5717-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1145\/1064092.1064116"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.4086\/toc.2012.v008a014"},{"volume-title":"Elements of statistical learning: data mining, inference, and prediction","author":"Hastie Trevor","unstructured":"Trevor Hastie , Robert Tibshirani , and Jerome Friedman . 2001. Elements of statistical learning: data mining, inference, and prediction . Springer . Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2001. Elements of statistical learning: data mining, inference, and prediction. Springer.","key":"e_1_3_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1145\/1007352.1007413"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1145\/1147954.1147955"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_3_2_1_23_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)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1137\/18M1229912"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 35th International Symposium on Computational Geometry (SoCG \u20192019)","author":"Khesin Andrey Boris","year":"2019","unstructured":"Andrey Boris Khesin , Aleksandar Nikolov , and Dmitry Paramonov . 2019 . Preconditioning for the geometric transportation problem . In Proceedings of the 35th International Symposium on Computational Geometry (SoCG \u20192019) . Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. 2019. Preconditioning for the geometric transportation problem. In Proceedings of the 35th International Symposium on Computational Geometry (SoCG \u20192019)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1007\/s00208-005-0745-0"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML \u20192015)","author":"Kusner Matt","year":"2015","unstructured":"Matt Kusner , Yu Sun , Nicholas Kolkin , and Kilian Weinberger . 2015 . From word embeddings to document distances . In Proceedings of the 32nd International Conference on Machine Learning (ICML \u20192015) . Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. 2015. From word embeddings to document distances. In Proceedings of the 32nd International Conference on Machine Learning (ICML \u20192015)."},{"volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"McGregor Andrew","unstructured":"Andrew McGregor and Daniel Stubbs . 2013. Sketching earth-mover distance on graph metrics . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 274\u2013286. Andrew McGregor and Daniel Stubbs. 2013. Sketching earth-mover distance on graph metrics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 274\u2013286.","key":"e_1_3_2_1_29_1"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS \u20192013)","author":"Mikolov Tomas","year":"2013","unstructured":"Tomas Mikolov , Ilya Sutskever , Kai Chen , Greg S Corrado , and Jeff Dean . 2013 . Distributed representations of words and phrases and their compositionality . In Proceedings of Advances in Neural Information Processing Systems (NIPS \u20192013) . 3111\u20133119. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Proceedings of Advances in Neural Information Processing Systems (NIPS \u20192013). 3111\u20133119."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1137\/1.9781611973075.92"},{"unstructured":"Jonas W Mueller and Tommi Jaakkola. 2015. Principal differences analysis: Interpretable characterization of differences between distributions. In Advances in Neural Information Processing Systems. 1702\u20131710.  Jonas W Mueller and Tommi Jaakkola. 2015. Principal differences analysis: Interpretable characterization of differences between distributions. In Advances in Neural Information Processing Systems. 1702\u20131710.","key":"e_1_3_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1137\/05064206X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1016\/0022-2836(70)90057-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.3115\/v1\/D14-1162"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1561\/9781680835519"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_3_2_1_38_1","volume-title":"Carlo Tomasi, and Leonidas J Guibas","author":"Rubner Yossi","year":"2000","unstructured":"Yossi Rubner , Carlo Tomasi, and Leonidas J Guibas . 2000 . The earth mover\u2019s distance as a metric for image retrieval. International journal of computer vision, 40, 2 (2000), 99\u2013121. Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. 2000. The earth mover\u2019s distance as a metric for image retrieval. International journal of computer vision, 40, 2 (2000), 99\u2013121."},{"volume-title":"Proceedings of the 42nd ACM Symposium on the Theory of Computing (STOC \u20192012)","author":"Sharathkumar R.","unstructured":"R. Sharathkumar and Pankaj K. Agarwal . 2012. A near-linear time \u220a -approximation algorithm for bipartite geometric matching . In Proceedings of the 42nd ACM Symposium on the Theory of Computing (STOC \u20192012) . R. Sharathkumar and Pankaj K. Agarwal. 2012. A near-linear time \u220a -approximation algorithm for bipartite geometric matching. In Proceedings of the 42nd ACM Symposium on the Theory of Computing (STOC \u20192012).","key":"e_1_3_2_1_39_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1137\/1.9781611974782.49"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1145\/2766963"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML \u20192018)","author":"Yaroslavtsev Grigory","year":"2018","unstructured":"Grigory Yaroslavtsev and Adithya Vadapalli . 2018 . Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under \u2113 _p-Distances . In Proceedings of the 35th International Conference on Machine Learning (ICML \u20192018) . Grigory Yaroslavtsev and Adithya Vadapalli. 2018. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under \u2113 _p-Distances. In Proceedings of the 35th International Conference on Machine Learning (ICML \u20192018)."},{"unstructured":"Arman Yousefi and Rafail Ostrovsky. 2014. Improved Approximation Algorithms for Earth-Mover Distance in Data Streams. arXiv preprint arXiv:1404.6287.  Arman Yousefi and Rafail Ostrovsky. 2014. Improved Approximation Algorithms for Earth-Mover Distance in Data Streams. arXiv preprint arXiv:1404.6287.","key":"e_1_3_2_1_43_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '22","name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519979","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":43,"alternative-id":["10.1145\/3519935.3519979","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519979","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}