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)$.