Approximate Nearest Neighbor Search For ell_p-spaces (2 < P < infty) Via Embeddings

Bartal Yair, Gottlieb Lee-ad. Arxiv 2015

[Paper]    
ARXIV

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<\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.

Similar Work

• Approximate Nearest Neighbor Search In ell_p
• On Fast Bounded Locality Sensitive Hashing
• Approximate Furthest Neighbor With Application To Annulus Query
• Approximate K-flat Nearest Neighbor Search