On low dimensional local embeddings
Ittai Abraham, Yair Bartal, Ofer Neiman · 2009
We study the problem of embedding metric spaces into low dimensional `p spaces while faithfully preserving distances from each point to its k nearest neighbors. We show that any metric space can be embedded into O(ep log2 k) p with k-local distortion of O((log k)/p). We also show that any ultrametric can be embedded into O(log k)/3 p with k-local distortion 1 + . Our embedding results have immediate applications to local Distance Oracles. We show how to preprocess a graph in polynomial time to obtain a data structure of O(nk1/t log2 k) bits, such that distance queries from any node to its k nearest neighbors can be answered with stretch O(t). 1