Lower Bounds on Locality Sensitive Hashing

DOI10.1137/050646858MaRDI QIDQ3544242zbMATH OpenOpenAlexFDO

Authors 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

locality sensitive hashinglower boundsnearest neighbor search

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5506204
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Tight lower bounds for data-dependent locality-sensitive hashing
• On the Distortion of Locality Sensitive Hashing
• Lattice-based locality sensitive hashing is optimal
• Beyond locality-sensitive hashing
• Locality-sensitive hashing without false negatives
• The distortion of locality sensitive hashing
• Locality-Sensitive Hashing Without False Negatives for l_p
• Locality-sensitive hashing scheme based on p-stable distributions

Cited in

(20)

• A new lattice sieving algorithm base on angular locality-sensitive hashing
• Why locality sensitive hashing works: a practical perspective
• Lower bounds on lattice sieving and information set decoding
• Locality sensitive hashing with extended differential privacy
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• Locality-Sensitive Hashing Without False Negatives for l_p
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Tight lower bounds for data-dependent locality-sensitive hashing
• scientific article; zbMATH DE number 1559577 (Why is no real title available?)
• CoveringLSH: locality-sensitive hashing without false negatives
• Sketching and embedding are equivalent for norms
• Locality-sensitive hashing without false negatives
• On the Distortion of Locality Sensitive Hashing
• The distortion of locality sensitive hashing
• Lattice-based locality sensitive hashing is optimal
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• Hypercube LSH for approximate near neighbors
• An Improved Algorithm Finding Nearest Neighbor Using Kd-trees
• Nearly optimal property preserving hashing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3544242)