Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions | Awesome Learning to Hash Add your paper to Learning2Hash

Awesome Learning to Hash

A webpage dedicated to the latest research on learning-to-hash, including state-of-the-art deep hashing models, all updated on a weekly basis. Maintained by Sean Moran.

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

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

A. Andoni, P. Indyk. FOCS 2006

[PDF] [Code] [Tutorial]    
FOCS

We present an algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O(dn 1c2/+o(1)) and space O(dn + n1+1c2/+o(1)). This almost matches the lower bound for hashing-based algorithm recently obtained in (R. Motwani et al., 2006). We also obtain a space-efficient version of the algorithm, which uses dn+n logO(1) n space, with a query time of dnO(1/c2). Finally, we discuss practical variants of the algorithms that utilize fast bounded-distance decoders for the Leech lattice

Similar Work