Beyond locality-sensitive hashing
From MaRDI portal
Abstract: We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R^d, our algorithm achieves O(n^{
ho} + d log n) query time and O(n^{1 +
ho} + d log n) space, where
ho <= 7/(8c^2) + O(1 / c^3) + o(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ell_1 norm with
ho <= 7/(8c) + O(1/c^{3/2}) + o(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).
Recommendations
- Optimal data-dependent hashing for approximate near neighbors
- Optimal hashing-based time-space trade-offs for approximate near neighbors
- Approximate nearest neighbors search without false negatives for \(l_2\) for \(c>\sqrt{\log\log n}\)
- A locality-sensitive hash for real vectors
- scientific article; zbMATH DE number 1775450
Cited in
(40)- Identifying an unknown code by partial Gaussian elimination
- Index structures for fast similarity search for real-valued vectors. I
- Global similarity preserving hashing
- Lower bounds on lattice sieving and information set decoding
- Locality sensitive hashing with extended differential privacy
- Fast spectral analysis for approximate nearest neighbor search
- An efficient sum query algorithm for distance-based locally dominating functions
- Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
- An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN
- Neighborhood preserving hashing and approximate queries
- Locality-Sensitive Hashing Without False Negatives for l_p
- Approximate Bregman near neighbors in sublinear time: beyond the triangle inequality
- Optimal data-dependent hashing for approximate near neighbors
- Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
- scientific article; zbMATH DE number 1003256 (Why is no real title available?)
- Tight lower bounds for data-dependent locality-sensitive hashing
- Lower Bounds on Locality Sensitive Hashing
- Optimal hashing-based time-space trade-offs for approximate near neighbors
- Parameter-free locality sensitive hashing for spherical range reporting
- On the Distortion of Locality Sensitive Hashing
- Fast cross-polytope locality-sensitive hashing
- Lattice-based locality sensitive hashing is optimal
- Hypercube LSH for approximate near neighbors
- scientific article; zbMATH DE number 7204982 (Why is no real title available?)
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- An efficient sum query algorithm for distance-based locally dominating functions
- Approximate nearest neighbors search without false negatives for \(l_2\) for \(c>\sqrt{\log\log n}\)
- On the hardness of approximate and exact (bichromatic) maximum inner product
- A refined analysis of LSH for well-dispersed data points
- Data-dependent hashing via nonlinear spectral gaps
- Locality-sensitive hashing scheme based on p-stable distributions
- Lattice Sieving via Quantum Random Walks
- Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems
- Polytopes, lattices, and spherical codes for the nearest neighbor problem
- Near neighbor search via efficient average distortion embeddings
- Improved space-efficient approximate nearest neighbor search using function inversion
- Sublinear data structures for nearest neighbor in ultra high dimensions
- On the practicality of quantum sieving algorithms for the shortest vector problem
- Finding shortest lattice vectors faster using quantum search
This page was built for publication: Beyond locality-sensitive hashing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384038)
