{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:53Z","timestamp":1750309313612,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"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":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649666","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"800-811","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Data-Dependent LSH for the Earth Mover\u2019s Distance"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0332-6332","authenticated-orcid":false,"given":"Rajesh","family":"Jayaram","sequence":"first","affiliation":[{"name":"Google Research, New York City, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0097-7981","authenticated-orcid":false,"given":"Erik","family":"Waingarten","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5852-902X","authenticated-orcid":false,"given":"Tian","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SOCG \u20192017)","author":"Agarwal Pankaj","year":"2017","unstructured":"Pankaj Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi Varadarajan, and Allen Xiao. 2017. Faster algorithms for the geometric transportation problem. In Proceedings of the 33rd International Symposium on Computational Geometry (SOCG \u20192017)."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 54nd ACM Symposium on the Theory of Computing (STOC \u20192022)","author":"Agarwal Pankaj K","year":"2022","unstructured":"Pankaj K Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao. 2022. Deterministic, near-linear \u220a -approximation algorithm for geometric bipartite matching. In Proceedings of the 54nd ACM Symposium on the Theory of Computing (STOC \u20192022)."},{"volume-title":"Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC \u20192014)","author":"Agarwal Pankaj K.","key":"e_1_3_2_1_3_1","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."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748049"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_3_2_1_6_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."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.94"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634150"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746552"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017)","author":"Andoni Alexandr","year":"2017","unstructured":"Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. 2017. Optimal Hashing-based Time\u2013Space Trade-offs for Approximate Near Neighbors. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017). Available as arXiv:1608.03580"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188846"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00024"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry (SoCG \u20192016)","author":"Andoni Alexandr","year":"2016","unstructured":"Alexandr Andoni and Ilya Razenshteyn. 2016. Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG \u20192016). 9:1\u20139:11. Available as arXiv:1507.04299"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Hengjie Zhang. 2023. Sub-quadratic (1+\u03b5)-approximate Euclidean Spanners with Applications.","DOI":"10.1109\/FOCS57990.2023.00014"},{"key":"e_1_3_2_1_17_1","volume-title":"International conference on machine learning. 214\u2013223","author":"Arjovsky Martin","year":"2017","unstructured":"Martin Arjovsky, Soumith Chintala, and L\u00e9on Bottou. 2017. Wasserstein generative adversarial networks. In International conference on machine learning. 214\u2013223."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3524985"},{"key":"e_1_3_2_1_19_1","volume-title":"International Conference on machine learning. 497\u2013506","author":"Backurs Arturs","year":"2020","unstructured":"Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. 2020. Scalable nearest neighbor search for optimal transport. In International Conference on machine learning. 497\u2013506."},{"key":"e_1_3_2_1_20_1","unstructured":"Ainesh Bakshi Piotr Indyk Rajesh Jayaram Sandeep Silwal and Erik Waingarten. 2023. A Near-Algorithm for the Chamfer Distance. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582120"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Lorenzo Beretta and Aviad Rubinstein. 2023. Approximate Earth Mover\u2019s Distance in Truly-Subquadratic Time. arXiv preprint arXiv:2310.19514.","DOI":"10.1145\/3618260.3649629"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 36rd Annual Conference on Learning Theory (COLT \u20192023)","author":"Charikar Moses","year":"2023","unstructured":"Moses Charikar, Beidi Chen, Christopher R\u00e9, and Erik Waingarten. 2023. Fast Algorithms for a New Relaxation of Optimal Transport. In Proceedings of the 36rd Annual Conference on Learning Theory (COLT \u20192023)."},{"key":"e_1_3_2_1_27_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 4831\u20134862","author":"Charikar Moses","year":"2023","unstructured":"Moses Charikar, Beidi Chen, Christopher R\u00e9, and Erik Waingarten. 2023. Fast Algorithms for a New Relaxation of Optimal Transport. In The Thirty Sixth Annual Conference on Learning Theory. 4831\u20134862."},{"key":"e_1_3_2_1_28_1","unstructured":"Moses Charikar and Erik Waingarten. 2022. Polylogarithmic Sketches for Clustering. In International Colloquium on Automata Languages and Programming (ICALP \u20192022). 38:1\u201338:20."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585168"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519979"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585170"},{"key":"e_1_3_2_1_33_1","volume-title":"Robert Krauthgamer, and Pavel Vesel\u1ef3.","author":"Czumaj Artur","year":"2023","unstructured":"Artur Czumaj, Guichen Gao, Shaofeng H-C Jiang, Robert Krauthgamer, and Pavel Vesel\u1ef3. 2023. Fully Scalable MPC Algorithms for Clustering in High Dimension. arXiv preprint arXiv:2307.07848."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00050"},{"volume-title":"Proceedings of the 20th ACM Symposium on Computational Geometry (SoCG \u20192004)","author":"Datar Mayur","key":"e_1_3_2_1_35_1","unstructured":"Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th ACM Symposium on Computational Geometry (SoCG \u20192004). 253\u2013262."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00078"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_1_41_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)."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.139"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392350"},{"key":"e_1_3_2_1_44_1","volume-title":"Woodruff","author":"Kane Daniel M.","year":"2010","unstructured":"Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010. On the exact space complexity of sketching and streaming small norms. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192010)."},{"key":"e_1_3_2_1_45_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)."},{"key":"e_1_3_2_1_46_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)."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_20"},{"key":"e_1_3_2_1_48_1","first-page":"5","article-title":"Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)","volume":"6","author":"O\u2019Donnell Ryan","year":"2014","unstructured":"Ryan O\u2019Donnell, Yi Wu, and Yuan Zhou. 2014. Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny). ACM Transactions on Computation Theory, 6, 1 (2014), 5.","journal-title":"ACM Transactions on Computation Theory"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14-1162"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680835519"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210050"},{"key":"e_1_3_2_1_52_1","article-title":"A near-\u03b5-approximation algorithm for bipartite geometric matching","volume":"67","author":"Sharathkumar R.","year":"2020","unstructured":"R. Sharathkumar and Pankaj K. Agarwal. 2020. A near-\u03b5-approximation algorithm for bipartite geometric matching. J. ACM, 67, 3 (2020), 18:1\u201318:19.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.49"},{"key":"e_1_3_2_1_54_1","unstructured":"Arman Yousefi and Rafail Ostrovsky. 2014. Improved Approximation Algorithms for Earth-Mover Distance in Data Streams. arXiv preprint arXiv:1404.6287."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649666","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649666","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:51Z","timestamp":1750291431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649666"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":54,"alternative-id":["10.1145\/3618260.3649666","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649666","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}