47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions Berkeley, California October 21-October 24 ISBN: 0-7695-2720-5
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.49
We present an algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O\left( {dn^{1/c^2 + o(1)} } \right) and space O\left( {dn + n^{1 + 1/c^2 + o(1)} } \right). This almost matches the lower bound for hashing-based algorithm recently obtained in [27]. We also obtain a space-efficient version of the algorithm, which uses dn+n log^{O(1)} n space, with a query time of dn^{O(1/c^2 )}. Finally, we discuss practical variants of the algorithms that utilize fast bounded-distance decoders for the Leech Lattice.
Citation:
Alexandr Andoni, Piotr Indyk, "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions," focs, pp.459-468, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb