{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:04Z","timestamp":1763467984956,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,4,1]],"date-time":"2010-04-01T00:00:00Z","timestamp":1270080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0448095"],"award-info":[{"award-number":["CCF-0448095"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0122581"],"award-info":[{"award-number":["CCR-0122581"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p>\n            We consider the problem of embedding a metric into low-dimensional Euclidean space. The classical theorems of Bourgain, and of Johnson and Lindenstrauss say that any metric on\n            <jats:italic>n<\/jats:italic>\n            points embeds into an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            )-dimensional Euclidean space with\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) distortion. Moreover, a simple \u201cvolume\u201d argument shows that this bound is nearly tight: a uniform metric on\n            <jats:italic>n<\/jats:italic>\n            points requires nearly logarithmic number of dimensions to embed with logarithmic distortion. It is natural to ask whether such a volume restriction is the only hurdle to low-dimensional embeddings. In other words, do\n            <jats:italic>doubling<\/jats:italic>\n            metrics, that do not have large uniform submetrics, and thus no volume hurdles to low dimensional embeddings, embed in low dimensional Euclidean spaces with small distortion?\n          <\/jats:p>\n          <jats:p>\n            In this article, we give a positive answer to this question. We show how to embed any doubling metrics into\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            ) dimensions with\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) distortion. This is the first embedding for doubling metrics into fewer than logarithmic number of dimensions, even allowing for logarithmic distortion.\n          <\/jats:p>\n          <jats:p>\n            This result is one extreme point of our general trade-off between distortion and dimension: given an\n            <jats:italic>n<\/jats:italic>\n            -point metric\n            <jats:italic>(V,d)<\/jats:italic>\n            with doubling dimension dim\n            <jats:italic>\n              <jats:sub>D<\/jats:sub>\n            <\/jats:italic>\n            , and any target dimension\n            <jats:italic>T<\/jats:italic>\n            in the range \u03a9(dim\n            <jats:italic>\n              <jats:sub>D<\/jats:sub>\n            <\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            ) \u2264\n            <jats:italic>T<\/jats:italic>\n            \u2264\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ), we show that the metric embeds into Euclidean space R\n            <jats:italic>\n              <jats:sup>T<\/jats:sup>\n            <\/jats:italic>\n            with\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            \u221a dim\n            <jats:italic>\n              <jats:sub>D<\/jats:sub>\n            <\/jats:italic>\n            \/\n            <jats:italic>T<\/jats:italic>\n            ) distortion.\n          <\/jats:p>","DOI":"10.1145\/1734213.1734215","type":"journal-article","created":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T14:14:06Z","timestamp":1272982446000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Ultra-low-dimensional embeddings for doubling metrics"],"prefix":"10.1145","volume":"57","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[{"name":"Microsoft Research, Silicon Valley Campus, Mountain view, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132557"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). ACM","author":"Abraham I.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375608"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137886"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060624"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/060670511"},{"volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Chan T.-H. H.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"volume":"15","volume-title":"Algorithms and Combinatorics","author":"Deza M. M.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","year":"2002","author":"Engebretsen L.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/48184.48193"},{"volume-title":"Proceedings of the 44th Symposium on the Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Gupta A.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Indyk P. and Matou\u0161ek J. 2004. Low-distortion embeddings of finite metric spaces. In Handbook of Discrete and Computational Geometry Second ed. J. E. Goodman and J. O'Rourke Eds. Chapman &amp; Hall\/CRC Chapter 8 xviii+1539.  Indyk P. and Matou\u0161ek J. 2004. Low-distortion embeddings of finite metric spaces. In Handbook of Discrete and Computational Geometry Second ed. J. E. Goodman and J. O'Rourke Eds. Chapman &amp; Hall\/CRC Chapter 8 xviii+1539.","DOI":"10.1201\/9781420035315.ch8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273347"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146412"},{"volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Konjevod G.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780607"},{"volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Krauthgamer R.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012093209450"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-17.1.178"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Lee J. R. and Naor A. 2003. Embedding the diamond graph in Lp and dimension reduction in L1. In Geometric and Functional Analysis (GAFA). Springer Verlag.  Lee J. R. and Naor A. 2003. Embedding the diamond graph in L p and dimension reduction in L 1 . In Geometric and Functional Analysis (GAFA). Springer Verlag.","DOI":"10.1007\/s00039-004-0473-8"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365733"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_42_1","volume-title":"Graduate Texts in Mathematics","volume":"212","author":"Matou\u0161ek J.","year":"2002"},{"key":"e_1_2_1_43_1","first-page":"589","article-title":"Bi-Lipschitz embeddings into low dimensional Euclidean spaces","volume":"31","author":"Matou\u0161ek J.","year":"1990","journal-title":"Comm. Math. Univers. Carolinae"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509996"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1734213.1734215","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1734213.1734215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:28Z","timestamp":1750250728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1734213.1734215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1145\/1734213.1734215"],"URL":"https:\/\/doi.org\/10.1145\/1734213.1734215","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2010,4]]},"assertion":[{"value":"2008-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}