{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:30:07Z","timestamp":1725507007491},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_4","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T04:38:35Z","timestamp":1207197515000},"page":"36-47","source":"Crossref","is-referenced-by-count":1,"title":["How to Complete a Doubling Metric"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"4_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans ${\\bf R}\\sp{n}$ . Bull. Soc. Math. France\u00a0111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: The 23rd International Conference on Machine Learning (ICML) (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"4_CR3","first-page":"8","volume-title":"Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms","author":"G. C\u0103linescu","year":"2001","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0-extension problem. In: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pp. 8\u201316. ACM Press, New York (2001)"},{"key":"4_CR4","unstructured":"Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in DOubling metrics. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 762\u2013771 (2005)"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"K.L. Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete Comput. Geom.\u00a022(1), 63\u201393 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: The thirty-eighth annual ACM symposium on Theory of computing (STOC) (2006)","DOI":"10.1145\/1132516.1132599"},{"key":"4_CR7","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S., Talwar, K.: An improved approximation algorithm for the 0-extension problem. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 257\u2013265. Society for Industrial and Applied Mathematics (2003)"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low\u2013distortion embeddings. In: Proceedings of the 44th Symposium on the Foundations of Computer Science (FOCS), pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"issue":"2","key":"4_CR9","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A. Gupta","year":"1999","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and \u21131-embeddings of graphs. Combinatorica\u00a024(2), 233\u2013269 (2004) (Preliminary version in 40th FOCS 1999)","journal-title":"Combinatorica"},{"key":"4_CR10","unstructured":"Gupta, A., Talwar, K.: How to complete a doubling metric (2008), http:\/\/arxiv.org\/abs\/0712.3331v1"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mendel, M.: Fast constructions of nets in low dimensional metrics, and their applications. In: Proceedings of the twenty-first annual symposium on Computational geometry, pp. 150\u2013158 (2005)","DOI":"10.1145\/1064092.1064117"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P., Naor, A.: Nearest neighbor preserving embeddings. In: ACM Transactions on Algorithms (to appear)","DOI":"10.1145\/1273340.1273347"},{"issue":"2","key":"4_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF02764938","volume":"54","author":"W.B. Johnson","year":"1986","unstructured":"Johnson, W.B., Lindenstrauss, J., Schechtman, G.: Extensions of lipschitz maps into banach spaces. Israel J. Math.\u00a054(2), 129\u2013138 (1986)","journal-title":"Israel J. Math."},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1006\/eujc.1997.0154","volume":"19","author":"A. Karzanov","year":"1998","unstructured":"Karzanov, A.: Minimum 0-extensions of graph metrics. European Journal of Combinatorics\u00a019(1), 71\u2013101 (1998)","journal-title":"European Journal of Combinatorics"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Klein, P., Plotkin, S.A., Rao, S.B.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the 25th ACM Symposium on the Theory of Computing (STOC), pp. 682\u2013690 (1993)","DOI":"10.1145\/167088.167261"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Optimal-stretch name-independent compact routing in doubling metrics. In: The twenty-fifth annual ACM symposium on Principles of distributed computing (2006)","DOI":"10.1145\/1146381.1146412"},{"key":"4_CR17","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Optimal scale-free compact routing schemes in doubling networks. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1145\/780542.780607","volume-title":"Proceedings of the thirty-fifth annual ACM symposium on Theory of computing","author":"R. Krauthgamer","year":"2003","unstructured":"Krauthgamer, R., Lee, J.R.: The intrinsic dimensionality of graphs. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 438\u2013447. ACM Press, New York (2003)"},{"key":"4_CR19","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 798\u2013807. Society for Industrial and Applied Mathematics (2004)"},{"issue":"11","key":"4_CR20","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1016\/j.crma.2004.03.005","volume":"338","author":"J. Lee","year":"2004","unstructured":"Lee, J., Naor, A.: Absolute lipschitz extendability. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences - Series I - Mathematics\u00a0338(11), 859\u2013862 (2004)","journal-title":"Comptes Rendus de l\u2019Acad\u00e9mie des Sciences - Series I - Mathematics"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Lee, J., Naor, A., Peres, Y.: Trees and Markov convexity. Geometric and Functional Analysis. Preliminary version in SODA (to appear, 2006)","DOI":"10.1145\/1109557.1109671"},{"key":"4_CR22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF02785579","volume":"114","author":"J. Matou\u0161ek","year":"1999","unstructured":"Matou\u0161ek, J.: On embedding trees into uniformly convex Banach spaces. Israel Journal of Mathematics\u00a0114, 221\u2013237 (1999); (Czech version in: Lipschitz distance of metric spaces, C.Sc. degree thesis, Charles University 1990).","journal-title":"Israel Journal of Mathematics"},{"issue":"1","key":"4_CR23","first-page":"99","volume":"31","author":"J. Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J.: Extension of Lipschitz mappings on metric trees. Commentationes Mathematicae Universitatis Carolinae\u00a031(1), 99\u2013104 (1990)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Rao, S.B.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In: 15th Annual ACM Symposium on Computational Geometry, pp. 300\u2013306 (1999)","DOI":"10.1145\/304893.304983"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: Algorithms for low-dimensional metrics. In: Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC), pp. 281\u2013290 (2004)","DOI":"10.1145\/1007352.1007399"}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:21:40Z","timestamp":1619508100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_4","relation":{},"subject":[]}}