Title: On Low Dimensional Local Embeddings

Authors: Ittai Abraham, Yair Bartal, Ofer Neiman

Abstract:

We study the problem of embedding metric spaces into low dimensional $L_p$ spaces while faithfully 
preserving distances from each point to its $k$ nearest neighbors. We show that any metric space can 
be embedded into $L^{O(e^p\log^2 k)}_p$ with $k$-local distortion of $O((\log k)/p)$. We also show 
that any ultrametric can be embedded into $L^{O(\log k/\epsilon^3}_p$ with $k$-local distortion 
$1+\epsilon$.

Our embedding results have imediate applications to local Distance Oracles. We show how to preprocess 
a graph in polynomial time to obtain a data structure of $O(n k^{1/t}\log^2 k)$ bites, such that 
distance queries from any node to its $k$ nearest neighbors can be answered with stretch $O(t)$.