Approximate Nearest Neighbor Search In ell_p

Nguyen Huy L.. Arxiv 2013

[Paper]    
ARXIV FOCS Independent LSH

We present a new locality sensitive hashing (LSH) algorithm for $c$-approximate nearest neighbor search in ${\ell }_p$ with $1<p<2$. For a database of $n$ points in ${\ell }_p$, we achieve $O(d{n}^{\rho })$ query time and $O(dn+n^{1+\rho })$ space, where $\rho \le O((\ln c{)}^2/c^p)$. This improves upon the previous best upper bound $\rho \le 1/c$ by Datar et al. (SOCG 2004), and is close to the lower bound $\rho \ge 1/c^p$ by O’Donnell, Wu and Zhou (ITCS 2011). The proof is a simple generalization of the LSH scheme for $\ell ₂$ by Andoni and Indyk (FOCS 2006).

Similar Work

• Beyond Locality-sensitive Hashing
• Approximate Nearest Neighbor Search For ell_p-spaces (2 < P < infty) Via Embeddings
• Lattice-based Locality Sensitive Hashing Is Optimal
• Multi-probe LSH Efficient Indexing For High-dimensional Similarity Search