MinHash — how does it estimate Jaccard similarity?
hardAnswer
- Given sets A, B: pick many random permutations of the universe.
- For each permutation, MinHash(A) = smallest element of A under that permutation.
- Fraction of permutations where MinHash(A) = MinHash(B) is an unbiased estimator of Jaccard(A, B) = |A ∩ B| / |A ∪ B|.
- Compact signature (128-256 hashes) enables billion-set comparison.
- Standard for near-duplicate detection in web crawlers (Bing, Google historically).
Check yourself — multiple choice
- Random
- Random permutations, min element of set as hash; fraction matching estimates Jaccard(A, B); 128-256 signature bytes enables billion-set comparison — web dedup standard
- Same as SimHash
- Not real
MinHash: min under random permutations; fraction match = Jaccard estimator.
#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?
- Locality-Sensitive Hashing (LSH) — the core trick.
- 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?