On the Distortion of Locality Sensitive Hashing

DOI10.1137/17M1127752MaRDI QIDQ4634022zbMATH OpenOpenAlexWikidataFDO

Authors Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, Erisa Terolli

Publication date 7 May 2019

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17m1127752

zbMATH Keywords

distortionlocality sensitive hashingsimilarity

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The distortion of locality sensitive hashing
• Beyond locality-sensitive hashing
• Locality-sensitive hashing without false negatives
• Locality-sensitive hashing scheme based on p-stable distributions
• Locality-Sensitive Hashing Without False Negatives for l_p
• scientific article; zbMATH DE number 5506204
• Lower Bounds on Locality Sensitive Hashing
• scientific article; zbMATH DE number 1559577
• Why locality sensitive hashing works: a practical perspective

Cites work

• Encyclopedia of Distances
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 3469876 (Why is no real title available?)
• scientific article; zbMATH DE number 1559577 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 3448387 (Why is no real title available?)
• scientific article; zbMATH DE number 1869496 (Why is no real title available?)
• Image steganalysis with binary similarity measures
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Lower Bounds on Locality Sensitive Hashing
• LSH-preserving functions and their applications
• Min-wise independent permutations
• Non-trivial intersecting families
• Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)
• Optimal hashing-based time-space trade-offs for approximate near neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Quantum information theory
• Similarity estimation techniques from rounding algorithms
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Successive refinement of information
• The complexity of LSH feasibility

Cited in

(14)

• A new lattice sieving algorithm base on angular locality-sensitive hashing
• Exploiting pseudo-locality of interchange distance
• Locality sensitive hashing with extended differential privacy
• Sharing hash codes for multiple purposes
• The complexity of LSH feasibility
• Locality-Sensitive Hashing Without False Negatives for l_p
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• LSH-preserving functions and their applications
• Lower Bounds on Locality Sensitive Hashing
• Locality-sensitive hashing without false negatives
• Toward Optimal Manifold Hashing via Discrete Locally Linear Embedding
• The distortion of locality sensitive hashing
• LSH-preserving functions and their applications
• Locality-sensitive bucketing functions for the edit distance

This page was built for publication: On the Distortion of Locality Sensitive Hashing

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