Online Embeddings
13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin/Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72043 https://orcid.org/0000-0002-7983-9524 |
| _version_ | 1826189921375748096 |
|---|---|
| author | Indyk, Piotr Magen, Avner Sidiropoulos, Anastasios Zouzias, Anastasios |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Indyk, Piotr Magen, Avner Sidiropoulos, Anastasios Zouzias, Anastasios |
| author_sort | Indyk, Piotr |
| collection | MIT |
| description | 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings |
| first_indexed | 2024-09-23T08:29:55Z |
| format | Article |
| id | mit-1721.1/72043 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:29:55Z |
| publishDate | 2012 |
| publisher | Springer Berlin/Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/720432022-09-30T09:24:54Z Online Embeddings Indyk, Piotr Magen, Avner Sidiropoulos, Anastasios Zouzias, Anastasios Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Indyk, Piotr Indyk, Piotr 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings We initiate the study of on-line metric embeddings. In such an embedding we are given a sequence of n points X = x [subscript 1],...,x [subscript n] one by one, from a metric space M = (X,D). Our goal is to compute a low-distortion embedding of M into some host space, which has to be constructed in an on-line fashion, so that the image of each x i depends only on x [subscript 1],...,x [subscript i] . We prove several results translating existing embeddings to the on-line setting, for the case of embedding into ℓ [subscript p] spaces, and into distributions over ultrametrics. 2012-08-08T19:20:45Z 2012-08-08T19:20:45Z 2010-08 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-15368-6 http://hdl.handle.net/1721.1/72043 Indyk, Piotr et al. “Online Embeddings.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Ed. Maria Serna et al. Vol. 6302. (Lecture Notes in Computer Science, 6302) Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. 246-259. https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1007/978-3-642-15369-3_19 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin/Heidelberg Other University Web Domain |
| spellingShingle | Indyk, Piotr Magen, Avner Sidiropoulos, Anastasios Zouzias, Anastasios Online Embeddings |
| title | Online Embeddings |
| title_full | Online Embeddings |
| title_fullStr | Online Embeddings |
| title_full_unstemmed | Online Embeddings |
| title_short | Online Embeddings |
| title_sort | online embeddings |
| url | http://hdl.handle.net/1721.1/72043 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT indykpiotr onlineembeddings AT magenavner onlineembeddings AT sidiropoulosanastasios onlineembeddings AT zouziasanastasios onlineembeddings |