A document can contain thousands of words.
Turn it into a set of shingles and that set may contain thousands of elements.
Comparing every set exactly against every other set becomes expensive quickly.
MinHash asks whether a much smaller signature can preserve enough of the set’s similarity geometry to make the search practical.
Quick Read
MinHash is a probabilistic technique for estimating Jaccard similarity between sets. Under the classic construction, the probability that two sets have the same minimum value under a random permutation equals their Jaccard similarity. Repeating the process produces a compact signature whose fraction of matching components estimates set similarity.
One-sentence answer: MinHash is lossy because it replaces a large set with a short signature, discarding almost all member identities while preserving an approximate measure of set overlap.
The Jaccard Question
For sets A and B, Jaccard similarity compares the size of their intersection with the size of their union.
If two sets share nearly all elements, Jaccard similarity approaches one. If they share almost none, it approaches zero.
The challenge is computational: exact comparison can require handling all elements of both sets.
The Minimum Is a Strange but Powerful Witness
Imagine applying one random permutation to the universe of possible elements and asking which element from each set appears first.
If the same element is first in both sets, that is a match.
The beautiful result is that the probability of that match equals the sets’ Jaccard similarity.
One random minimum is noisy. Many independent minima form a usable estimator.
A Signature Is a Compressed Set
Instead of storing every shingle for fast comparison, the system stores a fixed number of MinHash components.
Compare two signatures component by component.
The proportion of matches estimates their Jaccard similarity.
The source set has vanished from the fast path. Similarity evidence survives.
More Components Buy Lower Variance
A short signature is cheap but noisy.
A longer signature consumes more memory and computation but gives a more stable estimate.
The number of components becomes an error budget.
Documents Become Sets Through Shingling
Near-duplicate document detection often begins by splitting text into overlapping n-grams or shingles.
The document then becomes a set of local fragments.
That transformation is already lossy if counts and global order are discarded.
MinHash performs a second reduction: the shingle set becomes a signature.
Near-Duplicate Detection Is the Natural Use
Two web pages may differ in timestamps, navigation, advertisements or a few paragraphs while retaining almost the same substantive text.
Cryptographic hashes treat any byte difference as a completely different fingerprint.
MinHash instead preserves approximate set overlap, making it useful when the question is “how much content is shared?” rather than “are the bytes identical?”
MinHash and Cryptographic Hashing Own Different Questions
Cryptographic hashing preserves exact identity evidence and destroys similarity geometry.
MinHash deliberately preserves similarity geometry and does not provide cryptographic integrity guarantees.
The same word “hash” hides two very different receiver jobs.
Banding Turns Signatures Into Candidates
Large-scale systems often divide a MinHash signature into bands.
Items matching within at least one band become candidate near-neighbours.
This transforms approximate similarity into candidate generation and avoids comparing every pair.
The banding parameters control the familiar trade-off between false positives and false negatives.
False Positives and False Negatives Are Structural
A moderately similar pair can collide by chance and become a candidate.
A genuinely similar pair can fail to collide under a finite signature or an aggressive banding scheme.
The point is not to pretend these errors vanish.
The system chooses parameters so their rates fit the downstream verification budget.
Deduplication Uses MinHash as a Front Door
Exact deduplication can verify candidates after they are found.
MinHash helps avoid the impossible task of exact all-pairs comparison first.
This keeps ownership clean: Deduplication decides whether records collapse; MinHash supplies a compact similarity signal that helps decide which pairs deserve inspection.
Education: Similar Answers Can Share Structure Without Being Identical
Two students can produce answers that use different wording while sharing most conceptual components.
A teacher does not need exact textual equality to recognise structural similarity.
MinHash is not a teaching method, but it offers a useful computational analogy: similarity can survive after exact representation has been discarded.
A CivDJ View: Inspect What the Set Representation Already Lost
Forward: does the signature retrieve the near-duplicates the receiver needs?
Backward: what counts, order or context vanished when the source became a set?
Rotate: does similarity remain meaningful across short documents, boilerplate-heavy pages, languages and rare phrases?
A good MinHash pipeline audits both reductions: document to set, then set to signature.
When MinHash Is Exactly the Right Loss
Use it when set overlap is the meaningful similarity measure, collections are too large for exact all-pairs comparison, approximate candidate generation is acceptable, and shortlisted pairs can be verified more carefully downstream.
When MinHash Becomes Dangerous
- Order or frequency matters but the set representation discards it.
- Too few signature components create unstable estimates.
- Banding parameters miss important near-duplicates.
- Boilerplate dominates the shingle set.
- MinHash similarity is treated as proof of semantic equivalence.
- The candidate signature replaces the source record needed for verification.
A Practical MinHash Audit
- Set: what elements represent the source?
- Similarity: is Jaccard the right metric?
- Signature: how many MinHash components are retained?
- Banding: what candidate threshold behaviour is created?
- Boilerplate: are common fragments overwhelming the signal?
- Verification: how are candidate pairs checked?
- Source: is the original document retained?
Research Anchors
MinHash remains a standard locality-sensitive hashing technique for large-scale set similarity and near-duplicate detection. Contemporary large-corpus pipelines continue to use MinHash-style signatures and banding because they reduce the number of expensive pairwise comparisons while preserving useful overlap signals.
Continue Through eduKateSG
Continue with How Lossy Works | Hashing, How Lossy Works | Deduplication, and the companion article How Lossy Works | Locality-Sensitive Hashing.
Final Thought: The Set Disappears, but Its Overlap Geometry Can Remain
MinHash is useful because it does not try to remember the set.
It remembers enough to ask who looks like whom.