Approximate nearest neighbor search for ${\ell }_p$-spaces ($2<p<\infty$) via embeddings

Abstract

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and ${\ell }_1$, few non-trivial algorithms are known for ${\ell }_p$ when ($2<p<\infty$). In this paper, we revisit this fundamental problem and present approximate nearest-neighbor search algorithms which give the first non-trivial approximation factor guarantees in this setting.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1408.1789