TITLE   : Local Embeddings of Metric Spaces

AUTHORS : Ittai Abraham, 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 {\em 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 {\em local embeddings} of metric spaces and provide
embeddings with distortion depending solely on the local structure
of the space.