On the Distortion of Locality Sensitive Hashing

DOI10.1137/17M1127752zbMath1421.68022OpenAlexW2935512716WikidataQ125904319 ScholiaQ125904319MaRDI QIDQ4634022

Erisa Terolli, Flavio Chierichetti, Alessandro Panconesi, Ravi Kumar

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

similaritydistortionlocality sensitive hashing

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-trivial intersecting families
• Min-wise independent permutations
• The complexity of LSH feasibility
• Image steganalysis with binary similarity measures
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• LSH-Preserving Functions and Their Applications
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Lower Bounds on Locality Sensitive Hashing
• Similarity estimation techniques from rounding algorithms
• Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
• Quantum information theory
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Successive refinement of information
• Encyclopedia of Distances
• Geometry of cuts and metrics

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