Lattice-based locality sensitive hashing is optimal
From MaRDI portal
Abstract: Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (STOC `98) to give the first sublinear time algorithm for the c-approximate nearest neighbor (ANN) problem using only polynomial space. At a high level, an LSH family hashes "nearby" points to the same bucket and "far away" points to different buckets. The quality of measure of an LSH family is its LSH exponent, which helps determine both query time and space usage. In a seminal work, Andoni and Indyk (FOCS `06) constructed an LSH family based on random ball partitioning of space that achieves an LSH exponent of 1/c^2 for the l_2 norm, which was later shown to be optimal by Motwani, Naor and Panigrahy (SIDMA `07) and O'Donnell, Wu and Zhou (TOCT `14). Although optimal in the LSH exponent, the ball partitioning approach is computationally expensive. So, in the same work, Andoni and Indyk proposed a simpler and more practical hashing scheme based on Euclidean lattices and provided computational results using the 24-dimensional Leech lattice. However, no theoretical analysis of the scheme was given, thus leaving open the question of finding the exponent of lattice based LSH. In this work, we resolve this question by showing the existence of lattices achieving the optimal LSH exponent of 1/c^2 using techniques from the geometry of numbers. At a more conceptual level, our results show that optimal LSH space partitions can have periodic structure. Understanding the extent to which additional structure can be imposed on these partitions, e.g. to yield low space and query complexity, remains an important open problem.
Recommendations
Cites work
- A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
- A mean value theorem in geometry of numbers
- Approximate nearest neighbor: towards removing the curse of dimensionality
- Beyond locality-sensitive hashing
- Efficient algorithms for substring near neighbor problem
- Efficient bounded-distance decoding of the hexacode and associated decoders for the Leech lattice and the Golay code
- Finding a closest point in a lattice of Voronoi's first kind
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- Lattice Coverings of Space: The Minkowski-Hlawka Theorem
- Lattices Which Are Good for (Almost) Everything
- Locality-sensitive hashing scheme based on p-stable distributions
- Lower Bounds on Locality Sensitive Hashing
- Minkowski's Convex Body Theorem and Integer Programming
- New directions in nearest neighbor searching with applications to lattice sieving
- Optimal data-dependent hashing for approximate near neighbors
- Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
- Short paths on the Voronoi graph and closest vector problem with preprocessing
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
- Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
- The closest vector problem in tensored root lattices of type A and in their duals
- The Measure of the Set of Admissible Lattices
Cited in
(12)- On the kernel of the theta operator mod \(p\)
- A new lattice sieving algorithm base on angular locality-sensitive hashing
- Why locality sensitive hashing works: a practical perspective
- Optimal data-dependent hashing for approximate near neighbors
- Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Lower Bounds on Locality Sensitive Hashing
- Fast cross-polytope locality-sensitive hashing
- Hypercube LSH for approximate near neighbors
- A refined analysis of LSH for well-dispersed data points
- Locality-sensitive hashing scheme based on p-stable distributions
- Polytopes, lattices, and spherical codes for the nearest neighbor problem
This page was built for publication: Lattice-based locality sensitive hashing is optimal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993309)
