Wait, What?
The probability that two sets choose the same minimum under a random ordering is exactly their Jaccard similarity.
MinHash is memorable because one small probabilistic identity unlocks a scalable similarity method. Instead of comparing enormous sets directly, build compact signatures whose agreement rate estimates Jaccard similarity. The method also provides a clean bridge from probability to locality-sensitive hashing and large-scale candidate retrieval.
Quick Answer
Learn MinHash through sets → Jaccard similarity → union and intersection → random permutation → minimum element → collision probability → repeated hashes → signature agreement → variance → LSH banding.
1. Own Jaccard Similarity First
For sets A and B, Jaccard similarity is |A ∩ B| / |A ∪ B|. Work several tiny examples by hand. MinHash estimates this specific set-overlap quantity; it is not a generic cosine-similarity or edit-distance estimator.
2. Imagine One Random Permutation
Randomly order the universe and record the first element from each set under that order. The two minima match exactly when the first element encountered in A ∪ B belongs to A ∩ B. Every union element is equally likely to be first, so the collision probability is the fraction of union elements lying in the intersection—the Jaccard similarity.
3. Turn the Proof Into a Picture
Write the union elements on cards, mark which are shared, shuffle them, and reveal cards from the top. The first union card decides whether the two MinHash values match. Repeat several times. This physical trace makes the probability identity much easier to retain than a formula alone.
4. Real Implementations Use Hash Functions
Materialising random permutations of a huge universe is impractical. Implementations simulate independent or suitably random orderings with hash functions and retain the minimum hash value per signature component. The quality and independence assumptions of the hash family therefore belong to the evidence boundary.
5. One Minimum Is Too Noisy
A single collision is a Bernoulli observation. Build a signature from many independent MinHash components and estimate similarity by the fraction of matching components. More components reduce estimator variance at the cost of more memory and computation.
6. Separate Estimation From Retrieval
MinHash signatures let you estimate pairwise Jaccard similarity cheaply, but comparing every pair in a huge collection is still quadratic. Locality-sensitive hashing groups signature components into bands so that similar objects are more likely to become candidates for exact or finer comparison.
7. Banding Creates a Threshold-Like Trade-Off
Rows per band and number of bands control the probability that a pair becomes a candidate. More demanding bands suppress weak similarities but may miss useful pairs; more permissive banding increases recall and candidate volume. Learners should plot candidate probability against true similarity rather than memorising a banding recipe.
8. Shingling Determines What “Similar” Means
For documents, sets often contain word or character shingles. Changing shingle length changes the represented object before MinHash begins. A poor representation cannot be rescued by a perfect estimator. This is an important professional boundary between feature construction and the similarity algorithm itself.
Common Failure States
- Using MinHash to estimate a similarity measure other than Jaccard without justification.
- Confusing the minimum hash value with the minimum original token.
- Using one hash and treating its result as a stable similarity score.
- Claiming independence from a weakly constructed hash family.
- Comparing every signature pair and calling the whole pipeline scalable.
- Ignoring how shingling changes the semantic meaning of similarity.
Practice Ladder
- Compute Jaccard similarity for tiny sets.
- Shuffle a union and record MinHash collisions.
- Derive the collision-probability proof.
- Build signatures with several hash functions.
- Measure estimator error as signature length grows.
- Implement LSH banding and plot candidate probability.
- Compare different shingle representations for the same documents.
Learning Hall Boundary
This article owns MinHash and Jaccard-oriented locality-sensitive hashing. The existing nearest-neighbour article owns the broader ANN landscape, while sketching articles own other compressed statistical summaries.
Evidence Boundary
The classical MinHash identity assumes a random permutation, with practical implementations approximating that behaviour through hash families and optimized variants. Accuracy depends on signature length, hashing assumptions, representation and candidate-generation parameters. Report those choices alongside similarity results.
Professional rule: understand MinHash when you can derive the Jaccard collision identity from first principles and distinguish the estimator, the representation and the LSH retrieval layer as three separate jobs.
