publication . Other literature type . Preprint . Conference object . 2015

Optimal Data-Dependent Hashing for Approximate Near Neighbors

Alexandr Andoni; Ilya Razenshteyn;
  • Published: 05 Jan 2015
  • Publisher: Association for Computing Machinery (ACM)
Abstract
We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an $n$-point data set in a $d$-dimensional space our data structure achieves query time $O(d n^{\rho+o(1)})$ and space $O(n^{1+\rho+o(1)} + dn)$, where $\rho=\tfrac{1}{2c^2-1}$ for the Euclidean space and approximation $c>1$. For the Hamming space, we obtain an exponent of $\rho=\tfrac{1}{2c-1}$. Our result completes the direction set forth in [AINR14] who gave a proof-of-concept that data-dependent hashing can outperform classical Locality Sensitive Hashing (LSH). In contrast to [AINR14], the new bound is not only optimal, but in fact improves over the best (optimal)...
Subjects
arXiv: Computer Science::Databases
free text keywords: Computer Science - Data Structures and Algorithms, Data dependent, Nearest neighbor search, Hamming space, Euclidean space, Hash function, Data structure, Discrete mathematics, Locality-sensitive hashing, Mathematics, Combinatorics, Exponent

[AAKK14] Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, and Robert Krauthgamer. Spectral approaches to nearest neighbor search. In Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS '2014), 2014. [OpenAIRE]

[AINR14] Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '2014), pages 1018-1028, 2014.

tan2 α = 2 We would like to claim that the right-hand sides of (27) and (28) are quite close. For this it is sufficient to compare μ(A−1/2S) and μ(B−1/2S). Since

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue