Locality-Sensitive Hashing (LSH)
Definition
LSH uses special families of hashes where similar objects are more likely to fall into the same buckets.
The method enables approximate similarity search without comparing every vector exactly with every other. Different LSH families fit different distance measures.
Simply explained
How to intentionally sort similar things more frequently into the same drawer.
Why it matters in practice
Relevant for large similarity and deduplication problems.
Example from business
Document signatures are grouped by MinHash/LSH to find possible near-duplicates.
Limits and pitfalls
- Use normal cryptographic hash functions; wrong distance metric; do not measure recall loss.
Origin & history
Indyk and Motwani formalized LSH approaches for high-dimensional Approximate Nearest Neighbor Search in the late 1990s.
Use in mid-sized companies
- Possible application in SMEs: accelerate duplicate or similarity search in large inventories.
Frequently asked questions
Is LSH cryptographic hashing?
No. Is the search exact? Typically approximate.
Sources
- Approximate Nearest Neighbors · Indyk & Motwani (1998), Approximate Nearest Neighbors
Sources checked on 10.10.2026.
Editorially reviewed on: