Start here: the problem it solves#
TL;DRthe 30-second version
- The goal is to find similar items in a huge collection, where similarity means the two items share most of their features. Checking every pair is quadratic and does not scale.
- Similarity is measured with the Jaccard index: the size of the intersection divided by the size of the union of the two feature sets. It runs from 0 (nothing in common) to 1 (identical).
- MinHash replaces each set with a small signature. For each of k fixed hash functions, the signature slot is the smallest hash over the set's elements. The fraction of slots where two signatures agree estimates their Jaccard similarity.
- LSH banding splits each k-slot signature into b bands of r rows, hashes each band to a bucket, and calls two items a candidate pair if they share a bucket in any band. Similar items collide; dissimilar items rarely do.
- The result: instead of comparing all pairs, you compare only candidate pairs. The band and row counts tune how similar a pair must be to become a candidate.
A search engine crawls billions of pages and many are near-copies: mirror sites, syndicated articles, pages that differ only in a header or an ad. It wants to keep one and drop the rest. A plagiarism checker wants to find documents that share long passages. A team training a language model wants to remove duplicate text so the model does not overweight repeated content. In each case the task is the same: out of a giant pile of items, find the pairs that are highly similar.
The obvious method is to compare every pair. With a million items that is about five hundred billion comparisons, and each comparison itself walks two large sets. The cost grows with the square of the collection, so it falls over long before you reach real scale. You need a way to skip the overwhelming majority of pairs that are obviously unrelated, and spend effort only where two items might genuinely be close.
First we need to pin down what similar means, because the whole method is built around one specific definition.
The idea that almost works: keep a random sample#
Here is a first attempt that points in the right direction. If comparing full sets is too expensive, compare small samples of them instead. Pick a fixed rule for sampling, apply it to both sets, and estimate the overlap from the samples. The trick is choosing a rule so that the samples of two similar sets tend to look alike.
A random rule that works beautifully is this: hash every element of a set, and keep only the element with the smallest hash. That single kept element is a random sample of the set, because a good hash scatters elements uniformly, so the smallest hash is equally likely to belong to any element. Now compare two sets by this rule. They keep the same element exactly when the globally smallest-hashing element of their combined pool happens to sit in both sets at once.
That coincidence is not arbitrary. The smallest-hashing element of the union is equally likely to be any of the union's elements, and it lands in both sets precisely when it belongs to the intersection. So the chance the two sets keep the same element is the size of the intersection over the size of the union, which is exactly the Jaccard similarity. One kept element gives one yes-or-no clue about similarity. Repeat with many independent hash functions and count how often the clues say yes, and you have an estimate.
The mechanism: signatures, then bands#
MinHash and LSH are two stages of one pipeline. The first stage turns each set into a short signature. The second stage groups signatures so that similar ones meet. Let us build each stage precisely.
Stage one, the signature. Fix k hash functions once, and use the same k for every item. To build an item's signature, take each hash function in turn, apply it to every element of the item's set, and record the smallest result. Slot j of the signature is the minimum of hash function j over the set. After all k functions, the item is represented by k numbers, no matter how many elements it started with.
- For hash function j, compute hash(element) for every element in the set.
- Take the minimum of those values. That minimum becomes slot j of the signature.
- Repeat for all k hash functions. The k minimums are the item's MinHash signature.
- To estimate the Jaccard similarity of two items, count the slots where their signatures hold the same value, and divide by k.
The estimate has a known accuracy. Each slot is an independent yes-or-no trial that comes up yes with probability equal to the true Jaccard, so the count of matches is a binomial, and the standard error of the estimate shrinks with the square root of k. Doubling the accuracy costs four times the hash functions. That is why real systems use tens to a couple hundred hashes: enough to pin the estimate down, still tiny next to the original sets.
Stage two, the banding. Estimating similarity for one chosen pair is now cheap, but a large collection still has too many pairs to score them all. LSH avoids that by grouping items so that only promising pairs ever meet. Split each signature into b bands, each holding r consecutive slots, so that b times r equals k. Hash the r values of a band into a bucket. Do this for every band of every item. Two items are a candidate pair if, in at least one band, they hash to the same bucket.
A band collides only when all r of its slots match between two items. Matching one slot has probability equal to the Jaccard similarity s, so matching a whole band of r slots has probability s to the power r. With b bands, each an independent chance to collide, the probability that two items become a candidate is one minus the chance they miss in every band, which is one minus the quantity (1 minus s-to-the-r), all raised to the power b.
Go deeperThe S-curve, and how to tune the threshold
Plot the candidate probability against the true similarity s and you get an S-shaped curve. Below some similarity the curve hugs zero, so dissimilar pairs almost never become candidates. Above it the curve climbs toward one, so similar pairs almost always do. The steepness of the rise is what makes LSH a filter rather than a blur.
The midpoint of the curve, the similarity where a pair has a middling chance of becoming a candidate, sits near (1 over b) raised to the power (1 over r). This is the threshold you design for. Choose it to match the similarity you consider a real near-duplicate. More rows per band raise the bar for a single band to collide, sharpening the cutoff. More bands give more chances to collide, lowering the cutoff. Because b times r equals k, the two dials trade against each other for a fixed signature length.
The tuning has two kinds of error. A false positive is a dissimilar pair that collides anyway and wastes a full comparison. A false negative is a similar pair that misses in every band and is never checked, so a true duplicate slips through. Raising the threshold cuts false positives and admits more false negatives, and lowering it does the reverse. You pick the point that fits your tolerance, and you can widen r or b to trade compute for recall.
A worked example: two similar docs, one stranger#
Take three short documents as sets of words. Document A is the sentence about a quick brown fox jumping over a lazy dog. Document B swaps two words, leaping instead of jumping and sleepy instead of lazy, so it shares six of the ten combined words with A, a Jaccard similarity of 0.6. Document C is an unrelated sentence that shares only a word or two, a Jaccard near 0.14.
Build a signature for each with twelve hash functions. For each function, hash all of a document's words and keep the smallest value. Line up A's and B's signatures and count matches: they agree on about seven of the twelve slots, an estimate near 0.58, close to the true 0.6. Line up A and C and they agree on only one slot, an estimate near 0.08. The signatures already separate the near-duplicate from the stranger, using twelve numbers instead of the full word sets.
Now band the signatures. With twelve slots split into six bands of two rows each, hash every band of every document into a bucket. In at least one band, A and B hold the same two values, so they land in the same bucket and become a candidate pair. C never matches either of them in a full band, so it shares no bucket and stays out. The banding has turned the numeric estimate into a concrete decision: compare A and B, skip everything involving C.
12-slot signatures, band 3 = slots 5 and 6 · A and B match on both, so they share band 3's bucket
PredictTwo documents have a true Jaccard similarity of 0.9, but with b = 20 bands of r = 5 rows the LSH threshold sits near 0.55. Roughly how often will this pair be found as a candidate, and why?
Hint: A single band collides with probability s to the power r; think about all twenty bands together.
Almost always. One band matches with probability 0.9 to the fifth power, about 0.59, so a single band alone would miss this very similar pair four times out of ten. But there are twenty independent bands, and the pair is a candidate if any one of them collides. The chance all twenty miss is (1 minus 0.59) to the twentieth power, which is vanishingly small, so the pair is found essentially every time. This is the point of using many bands: each band is a weak test, but together they reliably catch pairs above the threshold. The same math is why a pair far below the threshold, whose per-band collision chance is tiny, stays out even across twenty tries.
Memory and speed#
The win is in the shape of the cost. Building a signature touches every element of a set once per hash function, so it is linear in the set size times k, done once per item. After that, every item is just k small numbers, and the expensive all-pairs comparison is replaced by bucketing.
- Signature memory is k values per item, fixed regardless of how large the original set is. A set of a million shingles and a set of ten both shrink to the same k numbers.
- Building all signatures is linear in the total data: for each item, k passes over its set. This is a one-time preprocessing cost, easily parallelized across items.
- Banding hashes b bands per item into buckets, which is linear in the number of items. Grouping by bucket is a hash-table operation, not a pairwise scan.
- Only candidate pairs get a full comparison. When most pairs are dissimilar, the candidate count is far below the n-squared all-pairs total, so the whole job runs close to linear in the collection size.
- The estimate's error falls with the square root of k, so accuracy is a memory dial: more hashes, tighter estimate, longer signature.
What you trade away
MinHash and LSH buy their speed with approximation, and every dial has a cost on the other side. There are three tensions worth naming before you reach for them.
- Signature length against accuracy and cost. A longer signature (more hash functions) tightens the similarity estimate, but the error only shrinks with the square root of k, so halving the error means quadrupling the work and memory. Past a point the extra hashes buy very little.
- Recall against false candidates. The band and row split sets an S-curve: more bands catch more true near-duplicates but also wave through more unrelated pairs, and fewer bands do the reverse. You cannot push both up at once, so you pick the similarity threshold you care about and accept the candidate rate it implies.
- Candidates are not answers. LSH hands you a shortlist, not a verdict. A candidate pair still needs a full comparison to confirm it, and a real near-duplicate can slip through if it happened to disagree in every band. When a miss is expensive, you widen the bands and pay for the extra checks.
Variants and sharp edges
- One permutation MinHash: computing k independent hashes per element is the main cost of building signatures. A single-hash scheme partitions one hash's range into k bins and takes the minimum in each bin, approximating k MinHashes with one pass. Densification fills empty bins so the estimate stays unbiased.
- Shingling for documents: text becomes a set by taking overlapping runs of k words or characters, called shingles or n-grams. Longer shingles make chance overlaps rarer, so similarity reflects shared phrasing rather than shared vocabulary.
- Weighted and generalized MinHash: plain MinHash treats a feature as present or absent. Weighted MinHash extends the estimate to multisets, where features carry counts, which matters when term frequency should influence similarity.
- SimHash is the cousin for cosine similarity: instead of set overlap, it hashes weighted feature vectors to a bit signature whose Hamming distance tracks angular distance. It is the tool when your notion of similarity is cosine rather than Jaccard.
- LSH Forest and multi-probe LSH tune recall without exploding the number of tables, by adapting how many buckets each query probes rather than fixing b and r rigidly up front.
How it differs from the other sketches
MinHash and LSH sit in the same family as the other small-memory sketches, but they answer a different question. Bloom and cuckoo filters answer whether one item is present. HyperLogLog answers how many distinct items there are. Count-Min answers how often an item appears. MinHash answers how similar two sets are, and LSH turns that into which pairs are worth comparing.
| Structure | Question it answers | What it stores |
|---|---|---|
| Bloom / cuckoo filter | Is this item in the set? | bits or fingerprints |
| HyperLogLog | How many distinct items? | registers of leading-zero counts |
| Count-Min sketch | How often does this item appear? | a grid of counters |
| MinHash + LSH | Which items are near-duplicates? | k minimum-hash signatures, banded into buckets |
The shared idea is the same across all of them: apply hash functions to elements and keep a tiny summary that preserves one property of the data. Bloom keeps membership, HyperLogLog keeps cardinality, Count-Min keeps frequency, MinHash keeps pairwise similarity. Choosing among them is choosing which question you need answered in small, fixed memory.
Where MinHash and LSH run in the wild
- Web-scale near-duplicate detection: the technique traces to work at AltaVista on finding and filtering near-duplicate web pages, and search crawlers still use it to keep one copy of syndicated or mirrored content.
- Training-data deduplication: pipelines that build corpora for large language models use MinHash LSH to drop near-duplicate documents, since repeated text skews what a model learns and wastes training compute.
- Plagiarism and content matching: document-similarity services shingle text and use LSH to surface candidate matches out of huge archives without an all-pairs scan.
- Recommendation and clustering: early Google News clustered articles by similarity using MinHash, and the same approach groups similar users or items when the signal is set overlap.
- Libraries and platforms: the datasketch library offers MinHash and MinHash LSH in Python, and Apache Spark's MLlib ships a MinHashLSH transformer for approximate similarity joins on large datasets.
Common misconceptions & gotchas
Does a MinHash signature tell me whether a specific item is in a set?
No. A signature summarizes a whole set for comparison with other sets. It estimates how similar two sets are, and it cannot answer membership of a single element. That is a different question, and a Bloom or cuckoo filter is the tool for it. What a MinHash signature preserves is set similarity, so membership is out of its reach.
Why not just take the minimum hash once instead of k times?
One minimum gives a single yes-or-no clue about similarity, which is far too noisy to trust. The estimate is the fraction of matching slots across the signature, and its error falls with the square root of the number of hash functions. You need many slots so the fraction settles near the true similarity. A single slot is right on average but wildly variable on any one pair.
Can LSH miss a pair that really is similar?
Yes, and this is by design. A similar pair becomes a candidate only if some band matches, and there is a small chance every band misses. That is a false negative, and its rate is set by the band and row counts. Adding bands lowers the miss rate at the cost of more false positives to filter. You tune the balance; you do not eliminate both errors at once.
Does a larger band count always help?
It lowers the similarity threshold, so more pairs become candidates. That catches more true near-duplicates but also lets more unrelated pairs through, and each of those costs a full comparison. Past a point you are paying to examine pairs that were never close. The right band and row counts come from your target similarity, not from making one number as large as possible.
QuizYou build MinHash signatures with k = 100 and estimate the similarity of two sets whose true Jaccard is 0.30. What does the estimate look like across many such pairs?
- It centers on 0.30, with a spread that would shrink if you raised k
- It is always exactly 0.30, because MinHash is deterministic
- It centers on 0.50, because signatures pull estimates toward the middle
- It is meaningless unless the two sets are the same size
Show answer
It centers on 0.30, with a spread that would shrink if you raised k — Each of the 100 slots matches with probability equal to the true Jaccard, 0.30, so the number of matches is a binomial with mean 30. The estimate, matches over 100, centers on 0.30 and is unbiased. Its spread is the binomial standard error, which shrinks with the square root of k, so a larger k tightens the estimate around 0.30. It is not exactly 0.30 on any single pair, because the slots are random trials; it is correct in expectation. Set sizes do not need to match, since Jaccard is defined over the union.
In an interview
Lead with the problem and the two-stage answer. Finding similar items in a huge collection is quadratic if you compare every pair. MinHash shrinks each item's feature set to a short signature whose matching fraction estimates Jaccard similarity, and LSH banding groups signatures so that only similar items share a bucket and become candidates. You compare only the candidates rather than every pair. Name where it runs: near-duplicate web pages, training-data deduplication, plagiarism detection.
Then give the core fact that makes MinHash work. For a single hash function, the probability that two sets share the same minimum hash equals their Jaccard similarity, because the smallest-hashing element of the union is equally likely to be any element and matches only when it lies in the intersection. Repeat over k hash functions and the matching fraction estimates the similarity, with error falling as the square root of k.
If pushed on LSH, explain the S-curve. Split the signature into b bands of r rows, and a pair is a candidate if any band matches on all r slots. The candidate probability is one minus (1 minus s-to-the-r) to the power b, an S-shaped curve whose midpoint sits near (1 over b) to the power (1 over r). You place that midpoint at your target similarity, trading b against r to sharpen or soften the cutoff. Then open the simulator: build two similar signatures, watch them agree on roughly their true Jaccard fraction, then band them and watch the similar pair collide into a candidate while the stranger stays out.
References & further reading
- Leskovec, Rajaraman & Ullman — Mining of Massive Datasets, Chapter 3: Finding Similar Items — the canonical treatment: shingling, MinHash, the Jaccard estimate, LSH banding, and the S-curve threshold
- Broder — On the Resemblance and Containment of Documents (1997) — the original MinHash idea, introducing resemblance as a set-intersection problem estimated by sampling minima
- Broder, Glassman, Manasse & Zweig — Syntactic Clustering of the Web (near-duplicate detection at AltaVista) — the web-scale application: shingling and sampling to find near-duplicate pages across a crawl
- datasketch — MinHash and MinHash LSH in Python — a widely used implementation, including LSH, LSH Forest, and weighted MinHash
- Apache Spark MLlib — Locality-Sensitive Hashing (MinHashLSH) — a production MinHashLSH transformer for approximate similarity joins on large datasets
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.