MinHash & Similarity Sketches

The Count-Min sketch answered "how often does each thing occur?" This lesson answers a question with a different shape — not about one set, but about the relationship between two: "how alike are these two sets?" How much do two users' watch histories overlap (for a recommendation)? Are these two documents near-duplicates (for deduplication or plagiarism)? Is this fingerprint the same as that one? Each is really asking: how big is the overlap between two sets, relative to their combined size?

The exact answer has a name — the Jaccard similarity:

J(A, B) = |A ∩ B| / |A ∪ B| — shared elements over total distinct elements (0 = disjoint, 1 = identical).

Computing it exactly is easy for small sets and brutal at scale, in two separate ways. First, each set can be enormous — a user's entire click history, every 4-gram in a web page — so intersecting two of them means holding both in memory and comparing them element by element. Second, and worse: if you have N sets and want to find which pairs are similar, comparing every pair is O(N²) — for a million documents that's about 500 billion comparisons, which is simply impossible.

MinHash (Andrei Broder, 1997, built to spot near-duplicate web pages at AltaVista) solves the first problem, and its partner LSH solves the second. The trick is startlingly simple: hash every element of a set and keep only the minimum. Do that with k hash functions and each set collapses to a fixed-size signature of k numbers — and the fraction of those numbers that two signatures share is the Jaccard similarity. In the picture below, sets A and B share 3 of their 7 combined elements (true J = 3/7 ≈ 0.43), and 3 of 7 min-hashes agree — recovering 3/7 exactly. This is the last of §8's five sketches, and it reuses an instinct you've now built four times.

Here is the entire idea, and it is one of the most beautiful facts in all of data structures. Pick one random hash function h. For a set S, define its min-hash as the smallest hash value over all its elements: minhash(S) = min over x in S of h(x). Now the claim:

P( minhash(A) = minhash(B) ) = J(A, B) — exactly.

The probability that two sets produce the same minimum equals their Jaccard similarity. Not approximately — exactly. Here's why, and it takes just one picture in your head. Pour both sets into their union A ∪ B and hash every element. Someone has the globally smallest hash — call it the winner. Because a good hash scatters values uniformly, the winner is equally likely to be any one of the |A ∪ B| elements. Now, that winner is the min-hash of set A exactly when it's in A, and the min-hash of B exactly when it's in B. So minhash(A) and minhash(B) are the same value precisely when the winner belongs to both sets — when it lands in A ∩ B. The chance of that is the number of shared elements over the size of the union: |A ∩ B| / |A ∪ B| = J. If instead the winner sits in A-only or B-only, the two sets pick different minimums and there's no match.

So a single min-hash is a biased coin: it comes up match with probability exactly J, and no match otherwise. That's the whole engine. Everything else — signatures, estimates, LSH — is just squeezing a good measurement out of that one coin. Measured on real data, the coin is honest: pairs built to have Jaccard 0.90, 0.60, 0.30, and 0.10 came up match about 0.88, 0.62, 0.36, and 0.15 of the time over a thousand hashes — the match rate tracking the true similarity. (The equality is exact when the hashes are idealized random permutations; fast practical hashes like a·x + b mod p are only close to that, which nudges low-similarity estimates slightly high — exactly the small upward drift you see in those numbers.) Play with the lab: place items in A, in both, or in B, then press new hash and watch the winner — and the verdict — flip as often as your sets overlap.

One coin flip tells you almost nothing — a single min-hash either matches or doesn't, a lonely 0 or 1. So you flip it many times. Run k independent hash functions over a set and keep k minimums: that ordered list of k numbers is the set's MinHash signature. To estimate the similarity of two sets, line up their signatures and count: est J = (number of positions where they agree) / k. It's an unbiased estimator — flip a coin with bias J many times and the fraction of heads converges to J.

How many hashes do you need? The estimate's standard error is √( J·(1−J) / k ), so accuracy improves with the square root of k — quadruple k to halve the error. Measured mean errors bear this out: at k = 16 the estimate was off by about 0.104, at k = 64 about 0.051, at k = 256 about 0.029, and at k = 1024 about 0.017. A few hundred hashes already pins the similarity to a couple of percent. And here's the payoff that makes MinHash a structure and not just a probability trick: the signature has a fixed size — k numbers — no matter whether the set had ten elements or ten million. Two sets that would take gigabytes to intersect directly are compared in O(k) by scanning two short signatures. (You can shrink them further with b-bit MinHash, which keeps only the low bits of each minimum.)

One practical bridge remains: MinHash compares sets, but a lot of what we want to compare is text. The standard move is shingling — turn a document into the set of its overlapping k-grams. Slide a window of, say, 4 characters across the text and collect every distinct 4-gram; two similar documents produce highly overlapping shingle sets, so their MinHash signatures are similar. It works cleanly: the sentences "the quick brown fox jumps over the lazy dog" and "…fox jumped…" differ by one word, and their 4-shingle sets have a true Jaccard of 0.795, which MinHash with k=256 estimated at 0.789; two unrelated sentences scored 0.000. Documents become sets, sets become signatures, and similarity becomes a fast count.

Signatures make a single comparison cheap, but they don't rescue you from the O(N²) wall. If you have a million documents and want every similar pair, comparing all signatures pairwise is still ~500 billion comparisons. You need a way to avoid looking at the pairs that obviously aren't similar. That's Locality-Sensitive Hashing (LSH), and for MinHash the classic recipe is banding.

Split each length-k signature into b bands of r rows (so k = b·r). Hash each band — its little r-number strip — into a bucket. Two sets become candidates if they land in the same bucket for at least one whole band, meaning all r of their min-hashes in some band agree. Then you only ever run the real comparison on candidate pairs. The magic is in the probability. If two sets have similarity s, the chance they agree on all r rows of a given band is sʳ; the chance they fail every one of the b bands is (1 − sʳ)ᵇ; so the chance they become a candidate is:

P(candidate) = 1 − (1 − sʳ)ᵇ

Plot that against s and you get a sharp S-curve with a threshold near (1/b)^(1/r) — for a 12-number signature split as 4 bands × 3 rows, the threshold sits around 0.63: pairs more similar than that almost always become candidates, and less similar pairs are almost always filtered out before you ever compare them. The two knobs let you place that cutoff: more rows r steepen the curve and raise the threshold (fewer candidates, higher precision); more bands b lower it (more candidates, higher recall). With a 128-number signature you might choose 16 bands of 8 (threshold ≈ 0.71), 32 bands of 4 (≈ 0.42), or 64 bands of 2 (≈ 0.12), depending on how similar "similar enough" is. Either way, the trillion-pair scan collapses to a handful of candidate pairs — the needles, found without the haystack.

MinHash plus LSH is the workhorse of set-similarity at scale. It began with near-duplicate web-page detection (Broder at AltaVista, then Google) and it never left: today deduplicating the web-scale corpora that train large language models is done with MinHash-LSH, because removing near-duplicate documents both improves the model and saves compute. It powers plagiarism and copy detection, recommendation (Jaccard over users' or items' interaction sets), entity resolution and record linkage, and malware / binary similarity. You rarely implement it by hand: Apache Spark ships MinHashLSH, Python's datasketch gives you MinHash and MinHashLSH, and Lucene/Elasticsearch expose a MinHash token filter. A cousin worth knowing by name is SimHash (Charikar, 2002), which does the same job for cosine similarity of weighted vectors rather than Jaccard of sets. And know when not to reach for it: if the sets are small, just compute the exact Jaccard; if you need semantic similarity of embeddings, that's cosine and vector search, not MinHash.

With similarity in hand, the whole sketch family of §8 is complete, and it snaps into a single picture. Five structures, four questions, one instinct — hash the item, keep a clever little summary, accept a bounded error to buy enormous space:

• Bloom / Cuckoo filter — cells are bits, combined with AND → membership (is x in the set?).
• HyperLogLog — cells are rank registers, combined with MAX → cardinality (how many distinct?).
• Count-Min — cells are counters, combined with MIN → frequency (how often?).
• MinHash — cells are min-hashes, and you compare two signatures → similarity (how alike are two sets?).

MinHash is the odd one out — the first four summarize one set to answer a query about it, while MinHash summarizes a set precisely so it can be compared to another. But it's the same bargain every time. Learn the instinct once and you have all five.

That closes the probabilistic-sketch arc of §8, and with it Route B from the section opener — trade exactness for space. Trace the whole line: membership (Bloom, Cuckoo) → cardinality (HyperLogLog) → frequency (Count-Min) → similarity (MinHash). Five structures, each the same deal — hash it, keep a tiny summary, accept a small and bounded error — and each one squeezes a firehose of data into a few kilobytes with a guarantee you can reason about.

What's left in §8 takes the other road. When you can't accept any error — when you need the exact documents that contain a word, ranked — you don't shrink the data, you change its geometry with an inverted index, and score matches with TF-IDF and BM25. That's the next lesson: exact text search, the structure behind every search bar. After it come skip lists and Merkle trees, and then the §8 checkpoint that ties the specialized indexes and sketches together. You've finished the sketches; now we go back to indexes that are exact — and pay for it in space instead of accuracy.