{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:56:29Z","timestamp":1757314589755},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_19","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"246-259","source":"Crossref","is-referenced-by-count":1,"title":["Online Embeddings"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Indyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Zouzias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Andoni, A., Onak, K.: Approximating Edit Distance in Near-Linear Time. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 199\u2013204 (2009)","key":"19_CR1","DOI":"10.1145\/1536414.1536444"},{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 184\u2013193 (1996)","key":"19_CR2","DOI":"10.1109\/SFCS.1996.548477"},{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 161\u2013168 (1998)","key":"19_CR3","DOI":"10.1145\/276698.276725"},{"issue":"1-2","key":"19_CR4","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J. Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz Embedding of Finite Metric Spaces in Hilbert space. Israel J. Math.\u00a052(1-2), 46\u201352 (1985)","journal-title":"Israel J. Math."},{"unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: Approximation Algorithms for the 0-extension Problem. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 8\u201316 (2001)","key":"19_CR5"},{"doi-asserted-by":"crossref","unstructured":"Englert, M., R\u00e4cke, H., Westermann, M.: Reordering Buffers for General Metric Spaces. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 556\u2013564 (2007)","key":"19_CR6","DOI":"10.1145\/1250790.1250871"},{"key":"19_CR7","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol.\u00a01. John Wiley & Sons, Chichester (January 1968)"},{"doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded Geometries, Fractals, and Low-Distortion Embeddings. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 534\u2013543 (2003)","key":"19_CR8","DOI":"10.1109\/SFCS.2003.1238226"},{"unstructured":"Gupta, A., Ravi, R.: Lecture Notes of Metric Embeddings and Methods (2003), http:\/\/www.cs.cmu.edu\/~anupamg\/metrics\/lectures\/lec10.ps","key":"19_CR9"},{"unstructured":"Indyk, P.: High-dimensional Computational Geometry. PhD thesis, Stanford University (2000)","key":"19_CR10"},{"doi-asserted-by":"crossref","unstructured":"Indyk, P.: Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 189\u2013197 (2000)","key":"19_CR11","DOI":"10.1109\/SFCS.2000.892082"},{"doi-asserted-by":"crossref","unstructured":"Indyk, P.: Tutorial: Algorithmic Applications of Low-distortion Geometric Embeddings. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 10\u201333 (2001)","key":"19_CR12","DOI":"10.1109\/SFCS.2001.959878"},{"doi-asserted-by":"crossref","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz Mappings into a Hilbert Space. In: Amer.Math. Soc. (ed.) Conference in Modern Analysis and Probability, pp. 189\u2013206 (1984)","key":"19_CR13","DOI":"10.1090\/conm\/026\/737400"},{"key":"19_CR14","doi-asserted-by":"crossref","first-page":"77","DOI":"10.4064\/fm-22-1-77-108","volume":"22","author":"M.D. Kirszbraun","year":"1934","unstructured":"Kirszbraun, M.D.: Uber die Zusammenziehenden und Lipschitzchen Transformationen. Fund. Math.\u00a022, 77\u2013108 (1934)","journal-title":"Fund. Math."},{"doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured Descent: A new Embedding Method for Finite Metrics. Geometric Aspects of Functional Analysis, 839\u2013858 (2005)","key":"19_CR15","DOI":"10.1007\/s00039-005-0527-6"},{"issue":"1","key":"19_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00222-004-0400-5","volume":"160","author":"J.R. Lee","year":"2005","unstructured":"Lee, J.R., Naor, A.: Extending Lipschitz Functions via Random Metric Partitions. Invent. Math.\u00a0160(1), 59\u201395 (2005)","journal-title":"Invent. Math."},{"issue":"2","key":"19_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The Geometry of Graphs and some of its Algorithmic Applications. Combinatorica\u00a015(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"19_CR18","first-page":"589","volume":"31","author":"J. Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J.: Bi-Lipschitz Embeddings into Low-dimensional Euclidean Spaces. Comment. Math. Univ. Carolinae\u00a031, 589\u2013600 (1990)","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"19_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, New York (2002)"},{"doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Sidiropoulos, A.: Inapproximability for Metric Embeddings into \u211dd. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 405\u2013413 (2008)","key":"19_CR20","DOI":"10.1109\/FOCS.2008.21"},{"unstructured":"Newman, I., Rabinovich, Y.: Personal communication (2008)","key":"19_CR21"},{"doi-asserted-by":"crossref","unstructured":"Rao, S.: Small Distortion and Volume Preserving Embeddings for Planar and Euclidean Metrics. In: Proceedings of the ACM Symposium on Computational Geometry (SoCG), pp. 300\u2013306 (1999)","key":"19_CR22","DOI":"10.1145\/304893.304983"},{"key":"19_CR23","series-title":"Lecture Notes in Artificial Intelligence","first-page":"265","volume-title":"Principles of Data Mining and Knowledge Discovery","author":"G. Schechtman","year":"2000","unstructured":"Schechtman, G.: The Random Version of Dvoretzky\u2019s Theorem in \u2113\u2009\u221e\u2009. In: Zighed, D.A., Komorowski, J., \u017bytkow, J.M. (eds.) PKDD 2000. LNCS (LNAI), vol.\u00a01910, pp. 265\u2013270. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:21Z","timestamp":1606187121000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}