Abraham, Ittai and Bartal, Yair and Neiman, Ofer (2007) Local Embeddings of Metric Spaces. In: STOC '07 Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 631-640. ISBN 978-1-59593-631-8. https://resolver.caltech.edu/CaltechAUTHORS:20160414-155818489
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160414-155818489
Abstract
In many application areas, complex data sets are often represented by some metric space and metric embedding is used to provide a more structured representation of the data. In many of these applications much greater emphasis is put on the preserving the local structure of the original space than on maintaining its complete structure. This is also the case in some networking applications where “small world” phenomena in communication patterns has been observed. Practical study of embedding has indeed involved with finding embeddings with this property. In this paper we initiate the study of local embeddings of metric spaces and provide embeddings with distortion depending solely on the local structure of the space.
Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
Additional Information: | © 2007 ACM. Supported in part by a grant from the Israeli Science Foundation (195/02). | |||||||||
Funders: |
| |||||||||
Subject Keywords: | Algorithms, Theory, Metric Embedding | |||||||||
Classification Code: | F.2.0 [Theory of Computation]: Analysis of Algorithms and Problem Complexity – General | |||||||||
DOI: | 10.1145/1250790.1250883 | |||||||||
Record Number: | CaltechAUTHORS:20160414-155818489 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20160414-155818489 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 66195 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | Kristin Buxton | |||||||||
Deposited On: | 14 Apr 2016 23:06 | |||||||||
Last Modified: | 10 Nov 2021 23:54 |
Repository Staff Only: item control page