Local Embeddings
of Metric Spaces
|
Yair Bartal Ofer Neiman |
|
|
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 his 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. |
|
|
[STOC version pdf] |
