Locality-Sensitive Hashing (LSH) — the core trick.
hardAnswer
- Hash function h such that P(h(x) = h(y)) is high for close x, y and low for far ones (opposite of crypto hash).
- Different metric → different LSH family: MinHash for Jaccard (near-duplicate documents), SimHash for cosine, random hyperplane for cosine, Euclidean via random projections.
- Multiple hash tables → high recall.
- Standard for near-duplicate detection in web crawls, genomic sequence search.
Check yourself — multiple choice
- Random
- Hash so P(h(x)=h(y)) is high for close pairs; MinHash for Jaccard (near-duplicates), SimHash for cosine, random hyperplane, random projection; near-duplicate detection standard
- Same as HNSW
- Not real
LSH: close pairs hash together; MinHash/SimHash/random hyperplane.
#applications#similarity
Practise Unsupervised Learning
214 interview questions in this topic.
Related questions
- HNSW — how does it work?
- Product Quantization (PQ) — how does it compress vectors?
- MinHash — how does it estimate Jaccard similarity?
- Interview: your image dataset (10M) has near-duplicates — how do you dedup at scale?
- How do you cluster mixed numeric + categorical data?
- Why do you scale features before k-means?