Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)

DOI10.1145/2578221zbMath1320.68095OpenAlexW1985289891MaRDI QIDQ2943898

Ryan O'Donnell, Yi Wu, Yuan Zhou

Publication date: 7 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2578221

zbMATH Keywords

noise sensitivitynoise stabilitylocality-sensitive hashingLSHFourier analysis of Boolean functions

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (16)

Sketching and Embedding are Equivalent for Norms ⋮ Lower bounds on lattice sieving and information set decoding ⋮ A new coding-based algorithm for finding closest pair of vectors ⋮ Nearly optimal property preserving hashing ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Lattice-based locality sensitive hashing is optimal ⋮ On the Distortion of Locality Sensitive Hashing ⋮ Index structures for fast similarity search for real-valued vectors. I ⋮ Index structures for fast similarity search for binary vectors ⋮ GLDH: toward more efficient global low-density locality-sensitive hashing for high dimensions ⋮ Unnamed Item ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Unnamed Item ⋮ Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}. ⋮ Local Density Estimation in High Dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Lower Bounds on Locality Sensitive Hashing
• Entropy based nearest neighbor search in high dimensions
• Efficient algorithms for substring near neighbor problem
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
• Locality-sensitive hashing scheme based on p-stable distributions

This page was built for publication: Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)