Lower Bounds on Locality Sensitive Hashing
From MaRDI portal
Publication:3544242
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
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