Comparing two huge sets element by element is slow, and comparing millions of pairs is hopeless. MinHash shrinks each set to a tiny signature of k numbers, then estimates similarity by comparing signatures. The magic property: for a single hash function, the probability that the two sets share the same minimum hash value is exactly their Jaccard similarity — the fraction of elements they have in common. Average over k hashes and you get a fast, accurate estimate. Add hashes and watch the estimate home in on the true overlap.
signature of k numbers · P(min matches) = Jaccard similarity · near-duplicate detection at scale
Jaccard similarity
|A ∩ B| / |A ∪ B| — the fraction of the combined elements that both sets share.
min-hash
For one hash function, the minimum hash value over all of a set’s elements.
signature
A set’s k min-hash values — a tiny fixed-size fingerprint, regardless of set size.
estimate
The fraction of the k signature positions where two sets’ min-hashes agree.
minhash.js — k minima, one similarity
Ready
Two sets with some overlap. Their true Jaccard similarity is fixed. Each Add hash computes one min-hash for each set: if the two minima match, that’s a vote for similarity. The match rate estimates Jaccard.
0
hashes (k)
–
estimate
0.33
true Jaccard
How it works
Here is why one min-hash matches with probability exactly the Jaccard similarity. Imagine hashing every element of the union A ∪ B and asking which element gets the smallest hash. That “winner” is equally likely to be any element of the union. The two sets share the same minimum if and only if that winning element lies in the intersection A ∩ B. So the match probability is |A ∩ B| / |A ∪ B| — the Jaccard similarity, by definition. Each hash is one Bernoulli trial with that success probability; averaging k of them estimates it.
1
Pick a hash function
Choose a hash that maps every possible element to a number, effectively a random permutation of the elements.
2
Take each set’s minimum
Hash every element of set A and keep the smallest value; do the same for set B. These are the two sets’ min-hashes for this hash function.
3
A match is a vote
If A’s minimum equals B’s minimum, the winning element is in the intersection — count it as a match. The chance of that is exactly the Jaccard similarity.
✓
Average over k hashes
Repeat with k independent hashes to build k-number signatures. The fraction of positions where the signatures agree estimates the Jaccard similarity, with accuracy improving as k grows.
Signature size
k numbers
P(match)
Jaccard
Estimate error
~1/√k
Used in
dedup, LSH
The code
# estimate Jaccard(A, B) with k min-hashesdef minhash_estimate(A, B, hashes):
matches = 0
for h in hashes: # k independent hash functions
min_a = min(h(x) for x in A) # set A's min-hash
min_b = min(h(x) for x in B) # set B's min-hashif min_a == min_b:
matches += 1 # the winner is in A ∩ Breturn matches / len(hashes) # ≈ |A∩B| / |A∪B|
Quick check
1. What does MinHash estimate?
MinHash estimates the Jaccard similarity |A∩B|/|A∪B|. The fraction of signature positions where two sets’ min-hashes agree converges to that value.
2. Why does one min-hash match with probability equal to the Jaccard similarity?
The element with the smallest hash over A∪B is uniformly random among union elements. The two sets share that minimum exactly when the winner is in A∩B, so the match probability is |A∩B|/|A∪B| — the Jaccard.
3. How does the estimate improve as you add more hashes?
Each hash is an independent Bernoulli trial with success probability equal to the Jaccard. Averaging k of them reduces the standard error like 1/√k, so more hashes tighten the estimate.
FAQ
What is MinHash?
A technique for quickly estimating the Jaccard similarity of two sets. Each set is represented by a signature of k values, each the minimum of a hash over the set’s elements. The fraction of signature positions where two sets agree estimates their Jaccard similarity — far faster than comparing elements directly.
What is Jaccard similarity?
The size of the intersection divided by the size of the union: |A∩B| / |A∪B|. It ranges from 0 (nothing shared) to 1 (identical) and measures the fraction of combined elements the two sets share.
How is MinHash used with Locality-Sensitive Hashing (LSH)?
MinHash produces each item’s signature; LSH buckets signatures so similar items likely collide, avoiding all-pairs comparison. The signature is split into bands, and items sharing any band become candidate matches — together they scale near-duplicate detection to billions of items.
Where is MinHash used in practice?
Near-duplicate web page and document detection (search index dedup), plagiarism detection, clustering, recommendation/collaborative filtering, and dataset deduplication — anywhere you must find similar items in a huge collection where exact pairwise comparison is too costly.