A Caltech Library Service

Local Embeddings of Metric Spaces

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.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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:
URLURL TypeDescription
Additional Information:© 2007 ACM. Supported in part by a grant from the Israeli Science Foundation (195/02).
Funding AgencyGrant Number
Israel Science Foundation195/02
Subject Keywords:Algorithms, Theory, Metric Embedding
Classification Code:F.2.0 [Theory of Computation]: Analysis of Algorithms and Problem Complexity – General
Record Number:CaltechAUTHORS:20160414-155818489
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66195
Deposited By: Kristin Buxton
Deposited On:14 Apr 2016 23:06
Last Modified:10 Nov 2021 23:54

Repository Staff Only: item control page