Lower Bounds on Locality Sensitive Hashing

DOI10.1137/050646858zbMath1158.68012OpenAlexW2002359780MaRDI 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 boundsnearest neighbor searchlocality sensitive hashing

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)

Related Items (12)

Sketching and Embedding are Equivalent for Norms ⋮ Lower bounds on lattice sieving and information set decoding ⋮ Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny) ⋮ 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 ⋮ Why locality sensitive hashing works: a practical perspective ⋮ An Improved Algorithm Finding Nearest Neighbor Using Kd-trees ⋮ Unnamed Item ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

This page was built for publication: Lower Bounds on Locality Sensitive Hashing