Lower Bounds on Locality Sensitive Hashing
From MaRDI portal
Publication:3544242
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
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)