Lower Bounds on Locality Sensitive Hashing

DOI10.1137/050646858zbMath1158.68012MaRDI QIDQ3544242

Assaf Naor, Rina Panigrahy, Rajeev Motwani

Publication date: 5 December 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.6628

zbMATH Keywords

lower bounds; nearest neighbor search; locality sensitive hashing

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Sketching and Embedding are Equivalent for Norms, On the Distortion of Locality Sensitive Hashing, Unnamed Item, Lattice-based locality sensitive hashing is optimal, On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic, An Improved Algorithm Finding Nearest Neighbor Using Kd-trees, Nearly optimal property preserving hashing, Why locality sensitive hashing works: a practical perspective, Lower bounds on lattice sieving and information set decoding, Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time, On closest pair in Euclidean metric: monochromatic is as hard as bichromatic, Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)