Lattice-based locality sensitive hashing is optimal

DOI10.4230/LIPIcs.ITCS.2018.42zbMath1462.68028arXiv1712.08558OpenAlexW2963560577MaRDI QIDQ4993309

Elena Grigorescu, Daniel Dadush, Venkata Gandikota, Karthekeyan Chandrasekaran

Publication date: 15 June 2021

Full work available at URL: https://arxiv.org/abs/1712.08558

zbMATH Keywords

random latticeslocality-sensitive hashingapproximate nearest neighbor search

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Lattices and convex bodies (number-theoretic aspects) (11H06) Data structures (68P05)

Uses Software

• FALCONN

Cites Work

• Unnamed Item
• Unnamed Item
• The closest vector problem in tensored root lattices of type A and in their duals
• A mean value theorem in geometry of numbers
• Finding a Closest Point in a Lattice of Voronoi's First Kind
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Optimal Data-Dependent Hashing for Approximate Near Neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Lattice Coverings of Space: The Minkowski-Hlawka Theorem
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• Lower Bounds on Locality Sensitive Hashing
• Lattices Which Are Good for (Almost) Everything
• Efficient algorithms for substring near neighbor problem
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
• Minkowski's Convex Body Theorem and Integer Programming
• Efficient bounded-distance decoding of the hexacode and associated decoders for the Leech lattice and the Golay code
• New directions in nearest neighbor searching with applications to lattice sieving
• A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
• Locality-sensitive hashing scheme based on p-stable distributions
• Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing
• Beyond Locality-Sensitive Hashing
• The Measure of the Set of Admissible Lattices

This page was built for publication: Lattice-based locality sensitive hashing is optimal