{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:41:26Z","timestamp":1787341286511,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100007277","name":"Center for Massive Data Algorithmics","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007277","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-144747"],"award-info":[{"award-number":["IIS-144747"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2022448"],"award-info":[{"award-number":["DMS-2022448"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>We study the problem of representing all distances between $n$ points in ${\\mathbb R}^d$, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for $\\ell_1$ (also known as Manhattan)-metrics, and for general metrics. Our bounds for Euclidean metrics mark the first improvement over compression schemes based on discretizing the classical dimensionality reduction theorem of Johnson and Lindenstrauss [ Contemp. Math. 26 (1984), pp. 189--206]. Since it is known that no better dimension reduction is possible, our results establish that Euclidean metric compression is possible beyond dimension reduction.<\/jats:p>","DOI":"10.1137\/20m1371324","type":"journal-article","created":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T11:04:07Z","timestamp":1652180647000},"page":"467-491","source":"Crossref","is-referenced-by-count":4,"title":["Optimal (Euclidean) Metric Compression"],"prefix":"10.1137","volume":"51","author":[{"given":"Piotr","family":"Indyk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tal","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,5,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"atypb3","volume-title":"Optimal Compression of Approximate Euclidean Distances, preprint, arXiv:1610.00239","author":"Alon N.","year":"2016"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"atypb6","first-page":"459","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006","author":"Andoni A.","year":"2006"},{"key":"atypb7","first-page":"184","volume-title":"Proceedings of the 37th Foundations of Computer Science, IEEE","author":"Bartal Y.","year":"1996"},{"key":"atypb8","first-page":"379","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE","author":"Charikar M.","year":"1998"},{"key":"atypb9","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages, and Programming","author":"Charikar M.","year":"2002"},{"key":"atypb10","first-page":"1","volume-title":"Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing","author":"Chechik S.","year":"2015"},{"key":"atypb12","volume-title":"Proceedings of the 37th International Conference in Machine Learning, JMLR","author":"Coleman B.","year":"2020"},{"key":"atypb13","volume-title":"Binarized Johnson-Lindenstrauss Embeddings, preprint, arXiv:2009.08320","author":"Dirksen S.","year":"2020"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"atypb15","first-page":"2946","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","author":"Ge T.","year":"2013"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.193"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21850"},{"key":"atypb19","first-page":"2614","volume-title":"Advances in Neural Information Processing Systems 30 Curran Associates","author":"Indyk P.","year":"2017"},{"key":"atypb20","first-page":"710","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM","author":"Indyk P.","year":"2017"},{"key":"atypb21","first-page":"2012","volume-title":"Proceedings of the 31st Conference On Learning Theory, JMLR","author":"Indyk P.","year":"2018"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483706"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"atypb24","volume-title":"Billion-Scale Similarity Search with GPUS, preprint, arXiv:1702.08734","author":"Johnson J.","year":"2017"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"atypb26","first-page":"2321","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","author":"Kalantidis Y.","year":"2014"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"atypb28","first-page":"633","volume-title":"Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE","author":"Larsen K. G.","year":"2017"},{"key":"atypb29","unstructured":"H. Le Nguyen,\n                      Algorithms for High Dimensional Data\n                      , Ph.D. thesis, Princeton University, 2014."},{"key":"atypb30","doi-asserted-by":"crossref","first-page":"1088","DOI":"10.1145\/3188745.3188828","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing","author":"Mahabadi S.","year":"2018"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761110"},{"key":"atypb32","volume-title":"Lecture Notes on Metric Embeddings, technical report","author":"Matou\u0161ek J.","year":"2013"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.12.001"},{"key":"atypb34","first-page":"1738","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM","author":"Molinaro M.","year":"2013"},{"key":"atypb35","first-page":"690","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM","author":"Naor A.","year":"2017"},{"key":"atypb36","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1145\/3313276.3316307","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","author":"Narayanan S.","year":"2019"},{"key":"atypb37","first-page":"3017","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","author":"Norouzi M.","year":"2013"},{"key":"atypb38","volume-title":"Proceedings of the 23rd International Conference on Database Theory (ICDT 2020","author":"Pagh R.","year":"2020"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"atypb40","volume-title":"Proceedings of the 7th International Conference on Learning Representations","author":"Sablayrolles A.","year":"2019"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2008.11.006"},{"key":"atypb42","unstructured":"A. Stollenwerk,\n                      One-Bit Compressed Sensing and Fast Binary Embeddings\n                      , Ph.D. thesis, RWTH Aachen University, Aachen, Germany, 2019."},{"key":"atypb43","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/SFCS.1984.715896","volume-title":"Proceedings of the 25th Annual Symposium on Foundations of Computer Science, IEEE, 1984","author":"Tarjan R.","year":"1984"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/100800774"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2015.2487976"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2699960"},{"key":"atypb48","first-page":"1753","volume-title":"Curran Associates","author":"Weiss Y.","year":"2009"},{"key":"atypb49","first-page":"202","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM","author":"C.","year":"2012"},{"key":"atypb50","volume-title":"Faster Binary Embeddings for Preserving Euclidean Distances, preprint, arXiv:2010.00712","author":"Zhang J.","year":"2020"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1371324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:41Z","timestamp":1787339561000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1371324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,10]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1137\/20M1371324"],"URL":"https:\/\/doi.org\/10.1137\/20m1371324","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,10]]}}}