Approximate Nearest Neighbor Search In ell_p | Awesome Learning to Hash Add your paper to Learning2Hash

Awesome Learning to Hash

A Webpage dedicated to the latest research on Hash Function Learning. Maintained by Sean Moran.

Contact Sean Moran about this survey or website. Made with Jekyll and Hyde.

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(dn^{\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 \(ℓ₂\) by Andoni and Indyk (FOCS 2006).

Similar Work