Optimal Data-Dependent Hashing for Approximate Near Neighbors

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 =\frac{1}{2c^2-1}$ for the Euclidean space and approximation $c>1$. For the Hamming space, we obtain an exponent of $\rho =\frac{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) LSH data structures [IM98,AI06] for all approximation factors $c>1$. From the technical perspective, we proceed by decomposing an arbitrary dataset into several subsets that are, in a certain sense, pseudo-random.

arXiv comment36 pages, 5 figures, an extended abstract appeared in the proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015)

Cited by in corpus (16)

• Probabilistic Polynomials and Hamming Nearest Neighbors
• Variance Reduced Stochastic Gradient Descent with Neighbors
• On the Resistance of Nearest Neighbor to Random Noisy Labels
• Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
• Hypercube LSH for approximate near neighbors
• Interpreting Shared Deep Learning Models via Explicable Boundary Trees
• Practical linear-space Approximate Near Neighbors in high dimension
• Set Similarity Search Beyond MinHash
• Randomized approximate nearest neighbor search with limited adaptivity
• Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities
• Discrete Latent Factor Model for Cross-Modal Hashing
• CoveringLSH: Locality-sensitive Hashing without False Negatives
• Approximate Near Neighbors for General Symmetric Norms
• A Refined Analysis of LSH for Well-dispersed Data Points
• LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System
• Distance-Sensitive hashing