Two documents can be almost the same even when their filenames, formatting or a few paragraphs differ. Comparing every pair of documents exactly becomes expensive when a collection contains millions of items. MinHash offers a compact mathematical shortcut: represent each set with a small random signature whose agreement rate estimates Jaccard similarity.
The surprising bridge is elegant. Under a random ordering of the universe, the probability that two sets have the same minimum-ranked element equals the size of their intersection divided by the size of their union. Repeat with independent random orderings or practical hash functions, and the fraction of matching signature positions becomes an estimator. This is why mathematics matters: a ratio about set overlap becomes a probability, then a scalable algorithm.
Choose Your Reading Route
- New learner* begin with sets, intersections and one shuffled ordering.
- Secondary student* focus on fractions, probability, sampling error and worked signatures.
- Computing student* study shingling, estimator variance, banding and hash assumptions.
- Parent or educator* use the card activity and misconception checks.
- Career explorer* read the search, plagiarism, web-crawling and recommendation sections before the FAQ.
Start with Jaccard Similarity
For two finite sets `A` and `B`, Jaccard similarity is:
`J(A,B)=|A intersection B| / |A union B|`.
It ranges from 0 to 1 when the union is non-empty. Identical sets have similarity 1. Disjoint sets have similarity 0.
Suppose `A={maths, data, graph, proof}` and `B={maths, data, proof, model}`. Their intersection has three elements and union has five, so Jaccard similarity is `3/5=0.6`.
Jaccard treats every distinct set element equally. It ignores multiplicity. If repeated words matter, use a multiset or weighted variant and state the definition.
Empty sets
If both sets are empty, the formula gives `0/0`. Applications choose a convention, often treating two empty sets as identical or handling them separately. If only one is empty, similarity is 0.
Edge-case policy is part of the specification. Do not let a library default silently determine meaning.
Documents Become Sets Through Shingling
A document is a sequence, not naturally a set. Convert it into shingles: contiguous sequences of characters or words. A word 3-shingle for “mathematics helps students learn” gives:
- mathematics helps students
- helps students learn
Longer documents produce many shingles. Nearby edits affect local shingles rather than every feature. Character shingles can detect similarity despite tokenisation differences; word shingles retain more linguistic structure.
Shingle length changes the question. Very short shingles create accidental overlap. Very long shingles miss similarity after small edits. There is no universally correct `k`; validate it on representative documents.
Set versus sequence information
Once shingles become a set, repeated occurrences and global order are mostly lost. Two documents with the same shingle set but different frequencies can appear identical under ordinary Jaccard similarity. MinHash preserves the chosen set similarity, not all properties of the original text.
This is responsible compression: define the property first, then preserve it approximately.
The Minimum Under a Random Ordering
Imagine giving every possible shingle a random rank. For a set `A`, its MinHash value is the member of `A` with the smallest rank.
Now consider `A union B`. Exactly one element has the smallest rank, ignoring ties. The minima for `A` and `B` are equal precisely when that globally smallest union element lies in `A intersection B`.
Every element of the union is equally likely to be minimum under a uniformly random permutation. Therefore:
`P[min(A)=min(B)] = |A intersection B| / |A union B| = J(A,B)`.
This proof is the heart of MinHash.
A card experiment
Write union elements on cards and shuffle them. Scan from the top. The first card belonging to either set is the minimum-ranked union element. Record whether it belongs to both sets. Repeat many shuffles. The fraction of “both” results approaches Jaccard similarity.
For the five-element example with intersection size three, the first union card is an intersection element with probability 3/5.
From One Bit of Evidence to a Signature
One random ordering yields one match or mismatch. Repeat `k` times. The signature of each set contains its minimum value under each ordering. Estimate similarity by the fraction of signature positions that match.
If two 100-position signatures match in 63 positions, estimate Jaccard similarity as 0.63.
Each position is approximately a Bernoulli trial with success probability `J`. The estimator is the sample mean.
Expectation and variance
Let `X_i=1` when signature position `i` matches and 0 otherwise. Then `E[X_i]=J`. The estimator `J_hat=(1/k) sum X_i` is unbiased under independent ideal permutations.
Its variance is `J(1-J)/k`. Standard error is `sqrt(J(1-J)/k)`. The worst case occurs near `J=0.5`, giving standard error at most `0.5/sqrt(k)`.
With `k=100`, worst-case standard error is 0.05. With `k=400`, it is 0.025. Halving standard error requires four times as many signature positions.
Approximate confidence interval
For sufficiently large `k` away from extreme probabilities, a rough 95% interval is `J_hat ± 1.96*SE`. If `J_hat=0.60` with `k=400`, estimated standard error is `sqrt(0.6*0.4/400)=0.0245`, giving roughly 0.552 to 0.648.
For small samples or values near 0 and 1, use a binomial interval such as Wilson rather than an uncorrected normal approximation.
Worked Signature Example
Let the universe be `{a,b,c,d,e}`. Set `A={a,b,c,d}` and `B={a,b,d,e}`. Intersection `{a,b,d}` has size 3; union has size 5; true Jaccard similarity is 0.6.
Use five orderings and record the first union element:
1. first is `a`, in both: match; 2. first is `c`, only A: mismatch; 3. first is `d`, in both: match; 4. first is `e`, only B: mismatch; 5. first is `b`, in both: match.
Three of five positions match, so estimate 0.6 exactly in this small sample. That agreement is luck, not a guarantee. Another five orderings could produce 0.4 or 0.8.
Sampling error is expected
An estimator can be unbiased and still differ from truth in one run. Unbiased means the average over repeated independent signatures equals the target, not that every signature is exact.
This distinction is central to statistics and honest AI evaluation.
Practical Hash Functions Replace Explicit Permutations
Generating a random permutation of a huge universe is impractical. Implementations use hash functions that assign pseudo-random ranks to shingles. For each signature position, choose a seed or hash function and keep the minimum hash value across the set.
The theory assumes sufficiently random, independent orderings. Real hash families approximate this. Correlated functions can increase estimator variance or bias. Seed reuse and implementation details should be documented.
Hash collisions
Two different shingles may receive the same finite hash value. A collision can create a false signature match. Wider hashes make accidental collisions rarer, but no finite hash eliminates them completely.
Do not confuse hash collision with shingle overlap. One is a representation accident; the other is the similarity signal.
Bottom-k sampling
Instead of many hash functions, hash each element once and keep the `k` smallest hashes. Bottom-k sketches can estimate set quantities and similarity with related mathematics. Their estimator and variance details differ, so do not quote classic independent-MinHash formulas without checking the variant.
The Original Resemblance Problem
Andrei Broder's foundational paper, On the Resemblance and Containment of Documents, developed sampling methods for large document collections using set resemblance and containment.
Resemblance corresponds to Jaccard similarity. Containment asks what fraction of one document's shingles appear in another. This matters when a short passage is copied into a much longer document: Jaccard similarity may be modest even though the short document is nearly contained.
Choose the metric according to the question. Near-duplicate pages, plagiarism fragments and template reuse can require different thresholds or containment measures.
Locality-Sensitive Hashing Narrows Candidate Pairs
MinHash makes one pair cheap to compare, but all pairs among `n` documents still number `n(n-1)/2`. For a million documents, that is about 500 billion pairs.
Locality-sensitive hashing groups signatures so similar items are likely to become candidates. A common banding scheme divides a signature into `b` bands of `r` rows. Two documents become a candidate if they match every row in at least one band.
If true similarity is `s`, assuming independent positions, probability of matching one entire band is `s^r`. Probability of no band match is `(1-s^r)^b`. Candidate probability is:
`1-(1-s^r)^b`.
Worked banding probabilities
Use `b=20` bands and `r=5` rows, total signature length 100.
For similarity 0.8, `s^r=0.32768`. Candidate probability is `1-(1-0.32768)^20`, over 0.9996.
For similarity 0.3, `s^r=0.00243`. Candidate probability is about `1-0.99757^20`, roughly 0.0475.
Banding creates an S-shaped response: high-similarity pairs become candidates often; low-similarity pairs less often. It is probabilistic, not a hard guarantee.
Threshold tuning
Increasing rows per band makes a band match stricter, reducing candidates. Increasing number of bands creates more chances, increasing candidates. For fixed signature length, the two parameters trade recall against candidate volume.
Validate with labelled pairs. A theoretical curve guides design but cannot determine the business cost of false positives and false negatives.
Near-Duplicate Detection Pipeline
A complete system might:
1. normalise document text; 2. generate shingles; 3. deduplicate shingles into a set; 4. compute MinHash signatures; 5. use banding to produce candidate pairs; 6. calculate exact Jaccard similarity for candidates; 7. apply a decision threshold and review policy.
Exact verification at the end prevents signature noise from becoming the final truth. MinHash reduces the search space; it need not make the irreversible decision.
Normalisation Is a Modelling Choice
Lowercasing, punctuation removal, stemming and boilerplate removal change shingles. If page headers are identical across a site, they can inflate similarity. If numbers are normalised, documents with different prices may appear closer.
Record the normalisation pipeline. For legal, academic or safety-sensitive use, preserve originals and explain which transformations are acceptable.
Mathematics cannot rescue a metric from an unsuitable representation. The set defines what “similar” means.
Search and Web Crawling
Search engines and crawlers encounter mirrored pages, print views, tracking parameters and copied content. Near-duplicate detection can reduce redundant indexing and improve diversity.
But two pages that share navigation and templates may have different central content. Content extraction or weighted features can be necessary. A similarity score should support, not replace, semantic and policy judgement.
Read content delivery networks, cache hit ratios, latency and invalidation for another place where identifying equivalent content affects system efficiency.
Plagiarism and Attribution
MinHash can help surface suspicious overlap, but it does not establish plagiarism. Legitimate quotations, common phrases, templates and independently written factual language can produce overlap. Conversely, paraphrase can evade surface shingles.
Human review needs source dates, context, citation practices and substantive comparison. A probabilistic candidate system should never be presented as automatic proof of misconduct.
This is a crucial age-appropriate lesson: similarity is evidence for review, not a moral verdict.
Recommendation and User Similarity
Represent a user by a set of interacted items and estimate Jaccard similarity between users. Similarity can support candidate recommendations.
However, set overlap ignores ratings, time and frequency. Popular items create broad overlap that may not reflect distinctive taste. Weighted Jaccard, cosine similarity or learned models may fit better.
Privacy matters. Compact signatures can still expose behavioural resemblance, and joining data across contexts may violate user expectations.
Set Size Imbalance
If set A has 10 elements and set B contains all 10 plus 990 more, intersection is 10 and union 1,000, so Jaccard similarity is 0.01. Yet A is fully contained in B.
Neither result is wrong. They answer different questions. Jaccard asks symmetric resemblance; containment asks asymmetric inclusion.
Always test metrics on scenarios that matter to users before choosing a threshold.
Weighted and One-Permutation Variants
Weighted MinHash extends the idea to non-negative feature weights and weighted Jaccard similarity. One-permutation and densification methods reduce hashing cost. SuperMinHash and other variants seek better speed or variance.
Each variant has its own proof and implementation details. A product named “MinHash” may not use independent full permutations. Read its documentation before calculating confidence or memory.
Memory and Compute Arithmetic
Suppose each signature has 128 entries of 64 bits. Raw signature storage is `128*8=1,024` bytes per document. For one million documents, that is about 1.024 GB decimal, before identifiers, indexes and overhead.
Using 32-bit values halves raw storage but increases hash-collision risk. Compression or b-bit MinHash can reduce space further while changing estimation error.
Computing signatures naively costs number of shingles times signature length. Practical methods batch hashing, use universal hash formulas, bottom-k sampling or hardware vectorisation.
Error Budgets for Decisions
Suppose the duplicate threshold is 0.8 and a 100-position signature gives estimate 0.81. Near the threshold, sampling uncertainty is too large for a confident automatic decision. Increase signature length, compute exact Jaccard for the candidate or route it for review.
An error budget should include:
- estimator sampling error;
- finite hash collisions;
- shingle and normalisation choices;
- candidate-generation misses;
- labelled-data uncertainty;
- consequences of a wrong decision.
The final item determines how cautious the pipeline should be.
Benchmarking MinHash Honestly
Use a dataset with known exact Jaccard values or human-labelled near-duplicate pairs. Measure signature estimation error, candidate recall, candidate precision, computation time and memory.
Stratify by document length and similarity range. A system can perform well on long similar pages but poorly on short documents. Report random seeds and repeat trials.
For banding, distinguish candidate recall from final duplicate classification. These are separate pipeline stages.
Common Misconceptions
“MinHash finds the minimum element in the original set”
It finds the minimum under a random or hashed ordering, not ordinary alphabetical or numeric order.
“Matching signatures prove sets are identical”
A finite signature estimates similarity probabilistically. Exact equality requires an exact check or additional evidence.
“MinHash measures semantic meaning”
It estimates overlap of the chosen features. Meaning depends on representation and context.
“More bands always improve detection”
More bands increase candidate probability for both similar and dissimilar pairs, raising work and potential false positives.
“A near-duplicate detector proves plagiarism”
It produces candidates for contextual review.
Which Mathematics Matters Most?
- sets, intersections and unions;
- ratios and Jaccard similarity;
- random permutations and symmetry;
- indicator variables and expectation;
- Bernoulli variance and standard error;
- binomial confidence intervals;
- exponent rules in banding probability;
- quadratic pair counts;
- hashing and finite representations.
The key transferable habit is to define similarity operationally. Before comparing scores, say what elements form each set and what information was removed.
A Practical Learning Progression
Stage 1: Calculate exact Jaccard
Use small word sets. Draw Venn diagrams and count intersection and union.
Stage 2: Shuffle cards
Create union cards, shuffle repeatedly and record whether the first card lies in the intersection.
Stage 3: Build signatures
Use ten predetermined orderings. Compare estimated similarity with exact Jaccard.
Stage 4: Quantify uncertainty
Repeat with 10, 50 and 200 signature positions. Plot absolute error across trials.
Stage 5: Add shingles
Convert short paragraphs into word 2-shingles and 4-shingles. Explain how `k` changes similarity.
Stage 6: Add banding
Calculate candidate probability curves for several `b,r` pairs and test them on labelled examples.
Guidance for Parents and Educators
Use transparent bags of word cards to represent documents. Intersection cards have the same colour in both bags. Shuffle a master union deck to demonstrate the minimum-event proof physically.
Ask students to distinguish target, estimator and decision. Target is exact Jaccard. Estimator is signature agreement. Decision is whether to investigate or label a pair. Conflating these layers creates overconfidence.
Encourage students to state one reason a high score could be misleading and one reason a low score could miss meaningful similarity. This develops evidence literacy alongside calculation.
Did You Know?
MinHash turns a set ratio into the probability of a shared minimum. That identity is useful because repeated probability experiments can be stored as a short signature.
The all-pairs problem grows quadratically. Doubling the number of documents roughly quadruples pair count. Candidate indexing is therefore as important as signature compression at large scale.
Student Projects
Near-duplicate notebook
Collect ten short public-domain paragraphs, make edited copies and compare exact Jaccard with MinHash estimates at several signature lengths.
Banding simulator
For a grid of `b,r` values, plot `1-(1-s^r)^b` from similarity 0 to 1. Mark desired recall thresholds.
Normalisation audit
Compare scores with and without lowercasing, punctuation removal and repeated header removal. Explain which transformation changes the intended question.
Confidence-aware interface
Show estimated similarity with an uncertainty interval and an “exact compare” button for borderline pairs.
FAQ
Is MinHash a cryptographic hash?
No. It uses hash-like random rankings for similarity estimation. Security properties are a separate requirement.
Why does only the minimum matter?
Under a random ordering, the minimum union element is uniformly distributed across union members. A match occurs exactly when it belongs to the intersection.
How long should a signature be?
Longer signatures reduce sampling variance but use more computation and storage. Choose length from the error and decision budget.
Can MinHash compare images?
It can compare sets of extracted image features, but usefulness depends on the feature representation. It does not inherently understand images.
Does locality-sensitive hashing change the estimate?
Banding usually selects candidate pairs. The underlying signature comparison or exact Jaccard supplies the similarity estimate.
What should a student remember?
Define sets, compute Jaccard, use random minima to build signatures, treat agreement as an estimate and verify high-stakes decisions.
Useful Next Reading
- Read Merkle trees, hash paths, inclusion proofs and efficient synchronisation to see hashes used for integrity rather than similarity.
- Read HNSW graphs, approximate nearest neighbours, recall and search cost for another approximate candidate-search design.
- Consult Broder's original document resemblance and containment paper.
Final Perspective
Worked Confidence and Threshold Example
Two documents have a 256-position signature with 205 matches. Estimated Jaccard similarity is `205/256≈0.8008`. Estimated standard error is `sqrt(0.8008*0.1992/256)≈0.0250`. A rough 95% normal interval is about 0.752 to 0.850.
If the duplicate threshold is 0.80, the signature alone does not justify a confident final label. It is excellent evidence for candidate generation, followed by exact comparison. If the exact shingle sets are available, calculate true Jaccard and avoid turning sampling uncertainty into policy uncertainty.
Now increase signature length to 4,096 with a similar match fraction. Standard error falls by a factor of four because sample size is sixteen times larger. Storage and computation also rise sixteen-fold. This square-root law is central to sampling design.
Wilson interval reminder
The normal interval can extend outside 0 to 1 or behave poorly with very few mismatches. A Wilson score interval remains within the probability range and generally has better coverage. Production confidence displays should use a justified binomial method rather than a classroom shortcut.
Updating and Deleting Documents
Changing one document requires recomputing its shingles and signature. The global LSH index must remove old band keys and insert new ones. Keeping stale buckets creates false candidates and can expose old content relationships.
Deletion should remove signature, bucket memberships and any cached exact features according to retention policy. Distributed indexes need tombstones or version checks so a delayed insertion does not resurrect a deleted version.
Document version is part of identity. Comparing signatures from different normalisation versions can be invalid even when file IDs match.
Multilingual and Code Collections
Word shingles depend on tokenisation. Languages without spaces, rich morphology and mixed scripts require appropriate segmentation. Character shingles may be more portable but can overemphasise orthographic overlap.
Source code needs language-aware normalisation choices. Renaming variables, formatting or reordering independent functions changes surface shingles differently. Token shingles can detect copied structure while comments and generated boilerplate may dominate unless handled.
Evaluate separately by language and content type. A single threshold rarely serves web pages, essays and code equally well.
Similarity Graphs
After candidate verification, documents can be vertices and high-similarity pairs edges. Connected components or clustering can group duplicate families. Transitivity is tricky: A may resemble B and B resemble C while A falls below the threshold with C.
Do not assume pairwise threshold similarity is an equivalence relation. Clustering policy—single-link, representative-based or complete-link—changes groups. Keep edge scores for audit rather than storing only a group label.
This is another place where graph mathematics follows probabilistic screening.
Containment Sketches and Asymmetric Questions
For sets A and B, containment of A in B is `|A intersection B|/|A|`. It is directional. If A is a short paragraph copied entirely into a long report, containment of A in B is 1 while containment of B in A may be small.
Jaccard similarity and set sizes can recover intersection size algebraically. Let `a=|A|`, `b=|B|`, `i=|A intersection B|` and `J=i/(a+b-i)`. Solving gives `i=J(a+b)/(1+J)`. With estimated J and known set sizes, estimate containment as `i/a`.
Error in J propagates nonlinearly, especially when sizes are very unequal. Direct containment-oriented methods or exact checking may be better near decision thresholds.
Worked imbalance example
Let A have 100 shingles and B have 1,000. If all A shingles appear in B, intersection is 100 and union is 1,000, so Jaccard is 0.1. Symmetric resemblance looks low, but containment of A in B is 1. The metric must follow the investigation question.
One-Hot Matrix View of the Proof
For a random permutation, mark the minimum-ranked union element with a one-hot indicator. Exactly one union coordinate is 1. A signature match occurs when that coordinate also belongs to the intersection.
By symmetry, each of the union's `u` elements has probability `1/u` of being minimum. Summing those probabilities across `i` intersection elements gives `i/u`.
This proof uses only symmetry of a uniform random ordering. It does not depend on document meaning, word frequency or element labels. That generality is why MinHash applies to many kinds of sets.
Covariance When Hashes Are Correlated
The variance formula `J(1-J)/k` assumes independent signature positions. If positions are correlated, variance of the average includes covariance terms:
`Var(mean) = (1/k^2)[sum Var(X_i) + 2 sum Cov(X_i,X_j)]`.
Positive correlation means the effective sample size is smaller than `k`. Using related seeds without validating the hash family can make an apparently long signature less informative.
Measure empirical variance across independent seed sets. Theory guides the expected result; experiment checks the implementation.
b-Bit MinHash
A full minimum hash value may use 32 or 64 bits. b-bit MinHash stores only the lowest `b` bits of each minimum, reducing memory. Unrelated minima can then match by chance with probability roughly related to `1/2^b`, requiring a corrected estimator.
For `b=1`, each entry is tiny but accidental agreement is common. For larger `b`, storage grows and correction shrinks. The method illustrates a second layer of compression: first replace a set with minima, then truncate each minimum.
Never apply the ordinary “fraction of matches equals Jaccard” formula directly to truncated signatures without the variant's correction.
Densification and Empty Bins
One-permutation schemes divide one hash range into bins and keep a minimum per bin. Small sets can leave many bins empty. Densification fills empty positions using values derived from non-empty bins under carefully designed rules.
Naive copying can introduce bias or correlation. Different densification methods have different guarantees. The implementation name is not enough; the paper or documentation should identify the estimator.
Candidate Buckets and Hot Spots
Banding inserts a document into one bucket per band using the band's row tuple as a key. Very common templates can create enormous buckets, producing too many candidate pairs.
Systems may cap buckets, remove boilerplate, use stop-shingles or split heavy buckets. Each choice can reduce work but also miss real duplicates. Monitor bucket-size distribution and candidate recall.
Suppose one bucket contains 100,000 documents. Pairing within it creates about five billion pairs. One pathological band can overwhelm the pipeline even if most buckets are small.
Multi-Probe and Index Tuning
Some locality-sensitive methods probe nearby buckets to recover candidates that narrowly miss an exact band match. This trades more query work for recall. For classic exact-band MinHash LSH, adjusting `b` and `r` is the simpler control.
Index design should include insertion volume, query volume, update frequency and deletion policy. A static web crawl and a live document editor need different maintenance plans.
Dataset Drift
Shingle distributions change as language, templates and content formats evolve. A threshold calibrated on news articles may fail on code, forms or chat messages. Periodically sample candidate and non-candidate pairs for exact or human review.
Track performance by source, language, length and date. A single global precision number can hide poor results for a minority group or short documents.
Privacy and Linkage Risk
A signature is smaller than the original set, but it still encodes similarity. An attacker with candidate sets can compute signatures under known seeds and test membership patterns. Shared seeds across organisations can enable unintended linkage.
Access control, seed management, retention limits and privacy analysis remain necessary. Random hashing is not anonymisation.
If signatures represent people, recommendations or behaviour, state the permitted purpose. Similarity infrastructure can become surveillance when contexts are joined without consent.
Adversarial Content
An attacker may add boilerplate shingles to lower Jaccard similarity, remove punctuation to alter tokenisation or deliberately seek hash collisions. Robust pipelines use multiple signals and exact review for consequential decisions.
Security goals differ from ordinary random-data accuracy. A non-cryptographic hash may satisfy estimator assumptions but permit deliberate collision construction. Choose according to the threat model.
Exact Verification at Scale
Once LSH returns candidate pairs, compute exact Jaccard using sorted shingle hashes or compressed bitmaps. Exact comparison cost is proportional to set sizes, but only candidates pay it.
The pipeline's efficiency comes from asymmetric effort: cheap approximate screening everywhere, expensive exact verification selectively. This pattern appears in spam filtering, medical screening and database query planning.
Keep the stages observable. Record how many items enter, how many candidate pairs emerge, how many pass exact threshold and how many survive human or policy review.
A Full Evaluation Protocol
Construct labelled pairs spanning exact duplicates, light edits, partial containment, shared templates, unrelated same-topic documents and adversarial rewrites. Include different lengths and languages.
For each signature length and banding setup, measure:
- estimator mean absolute error against exact Jaccard;
- confidence interval coverage;
- candidate recall at several exact-similarity thresholds;
- candidates generated per document;
- exact-verification workload;
- final precision and recall;
- memory and latency distributions.
Repeat seeds. Publish the normalisation and shingling configuration. Without those details, a “95% accurate” claim cannot be reproduced.
Error decomposition
When a true duplicate is missed, identify the stage:
- representation gave low exact Jaccard;
- finite signature underestimated similarity;
- banding failed to create a candidate;
- exact comparison used a different normalisation;
- final policy threshold rejected it.
Fixing the wrong stage can worsen the system.
A Complete Classroom Investigation
Create 20 base paragraphs and three edits of each: punctuation-only, ten-percent word changes and one inserted paragraph. Add 20 unrelated paragraphs. Calculate exact Jaccard for word 2-, 3- and 5-shingles.
Build signatures of length 20, 100 and 400 across 30 seeds. Plot estimation error. Then simulate banding and count candidate recall and workload. Finish with exact verification.
Students should recommend one configuration for a low-cost browsing tool and another for a high-stakes academic review system. The difference should be justified by consequences, not only speed.
Questions for Reading a Similarity Claim
- What elements form the sets?
- Is similarity symmetric or containment-based?
- Which normalisation and shingle length are used?
- How many signature samples are stored?
- What hash family and seed policy apply?
- Is LSH only candidate generation or the final decision?
- What exact verification and human review follow?
- How were precision and recall measured across groups?
MinHash shows why mathematics matters when a precise comparison is simple but too numerous to perform everywhere. Set theory defines resemblance. Symmetry turns overlap into a probability. Sampling compresses the evidence, and locality-sensitive hashing narrows the candidate space.
The larger lesson is both practical and humane: an approximation should support a decision, not impersonate certainty. Define the representation, quantify uncertainty and verify important cases. That habit lets students use scalable tools while remaining honest about what the tools actually know.