Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Top Cited Papers
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 459-468
- https://doi.org/10.1109/focs.2006.49
Abstract
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 latticeKeywords
This publication has 22 references indexed in Scilit:
- Locality-sensitive hashing scheme based on p-stable distributionsPublished by Association for Computing Machinery (ACM) ,2004
- Approximate graph coloring by semidefinite programmingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the optimality of the random hyperplane rounding technique for MAX CUTRandom Structures & Algorithms, 2002
- A replacement for Voronoi diagrams of near linear sizePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- Approximate nearest neighborsPublished by Association for Computing Machinery (ACM) ,1998
- Efficient search for approximate nearest neighbor in high dimensional spacesPublished by Association for Computing Machinery (ACM) ,1998
- Two algorithms for nearest-neighbor search in high dimensionsPublished by Association for Computing Machinery (ACM) ,1997
- Generalized minimum-distance decoding of Euclidean-space codes and latticesIEEE Transactions on Information Theory, 1996
- Sphere Packings, Lattices and GroupsPublished by Springer Nature ,1993
- Notes on Sphere PackingsCanadian Journal of Mathematics, 1967