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

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and ${\mathrm{\ell }}_1$, few non-trivial algorithms are known for ${\mathrm{\ell }}_p$ when ($2<p<\mathrm{\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.