Engineering Atlas › System Design Fundamentals

Estimating set similarity with MinHash

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

From documents to sets

Documents become sets of shingles: every run of n consecutive words (3 to 5) or characters (5 to 9). Mining of Massive Datasets suggests 5 characters for short texts such as emails and 9 for long documents, so that a random shingle is unlikely to appear by chance (MMDS ch. 3). "the quick brown fox" with word 2-grams becomes {"the quick", "quick brown", "brown fox"}. Small edits change only nearby shingles, so near-duplicates share most of their sets.

The MinHash property

Take a random hash function h and compute the minimum of h over set A and over set B. Think of h as randomly ordering the union of A and B. The element that comes first is equally likely to be any element of the union. Both minima are equal exactly when that first element lies in the intersection. So P[min h(A) = min h(B)] = |A ∩ B| / |A ∪ B|, the Jaccard similarity. Andrei Broder introduced this "resemblance" estimate in 1997 and tested it by clustering over 30 million pages from an AltaVista crawl at 50 percent resemblance (Broder).

Signatures

One hash gives a yes-or-no sample. Use k independent hash functions and store the k minima as the set's signature. The fraction of positions where two signatures agree estimates Jaccard similarity, with standard error about sqrt(J(1 - J) / k). With k = 128 the error is at most 0.044, at J = 0.5, and smaller near 0 or 1; datasketch's documentation quotes about 0.03 to 0.04 for its 128-value default (datasketch). A 128-entry signature of 32-bit values is 512 bytes regardless of document length.

Computing k hashes per shingle is the main cost, so production systems use cheaper variants. One-permutation hashing hashes each shingle once, splits the hash range into k bins and keeps the minimum per bin, with at least the accuracy of k separate hashes (Li, Owen and Zhang). Bottom-k hashes once and keeps the k smallest values overall. b-bit MinHash keeps only a few low bits of each value to shrink stored signatures.

LSH banding

With a billion documents, comparing all pairs of signatures is 5 × 10^17 comparisons. LSH avoids that. Split each signature of length k = b × r into b bands of r values. Hash each band to a bucket key. Two documents become a candidate pair if they share a bucket in at least one band.

The probability that a pair with similarity J becomes a candidate is 1 - (1 - J^r)^b. This is an S-curve: near zero for low J, near one for high J, with the threshold around (1/b)^(1/r) (MMDS ch. 3). Tuning b and r moves the threshold and steepens the curve. Candidates are then verified by comparing full signatures, or the actual documents.

Variants

Weighted MinHash handles term frequencies. SimHash, a different LSH family, approximates cosine similarity with a single 64-bit fingerprint.

Down the stack

Layer 1The contract

For any two sets, the expected fraction of matching signature positions equals their Jaccard similarity, with variance J(1 - J) / k. With LSH banding, a pair becomes a candidate with probability 1 - (1 - J^r)^b. Nothing is guaranteed about any specific pair: true duplicates can be missed and dissimilar pairs can collide, so candidates must be verified and recall measured.

Layer 2The mechanism

The Python library datasketch is a common reference. A MinHash holds num_perm values, 128 by default, and hashes each shingle with SHA-1 from Python's hashlib before applying the permutations (datasketch). Since version 2.0 (July 2026) each "permutation" is an affine map a * h + b mod 2^32 with an odd a, which is a bijection, and values are stored as 32-bit integers. Before 2.0 it was a universal hash modulo the Mersenne prime 2^61 - 1, stored in 64-bit slots. The change halved sketch memory and reduced an over-estimation bias, but hash values differ between versions, so persisted signatures and LSH indexes must be rebuilt or opened with scheme="legacy" (PyPI release notes).

MinHashLSH takes a similarity threshold and searches all (b, r) pairs for the one that minimises a weighted sum of false-positive and false-negative area under the S-curve. At num_perm = 128, weighting misses heavily gives 32 bands of 4, and weighting false positives heavily gives 16 bands of 8 (datasketch LSH). Its buckets can live in memory or in Redis or Cassandra for persistent indexes, and queries return unranked candidates that still need verification.

In batch pipelines, banding is a shuffle: each document emits b rows of (band index, band hash, doc ID), a group-by collects buckets, and a second pass emits candidate pairs and runs union-find over them.

Layer 3The machine

Signature computation is arithmetic-bound. With 1,000 shingles and 128 hashes, a document needs 128,000 multiply-add-mod operations. Vectorised over all 128 hash functions at once (NumPy or SIMD), that is around 50 to 200 us per document on one core, so a billion documents need tens of thousands of core-hours unless one-permutation hashing cuts the work about 100-fold.

Bytes dominate the distributed phase. With b = 20, a billion documents produce 20 billion band rows; at 16 bytes each (8-byte band hash, 8-byte doc ID) that is 320 GB written to local disk and sent across the network in the shuffle. Skew is the failure mode: one boilerplate bucket can land millions of rows on a single reducer, which then runs out of memory or straggles for hours while the rest of the cluster idles.

Why it's built this way

  1. Comparing every pair of documents is quadratic, so each document is reduced to a small fixed-size summary.
  2. The summary must estimate set overlap regardless of set size, which the minimum of a random hash does exactly.
  3. One minimum is a single coin flip, so k independent hashes reduce the variance.
  4. Even small signatures cannot be searched by similarity directly, so banding converts "similar" into "exactly equal band", which hash tables and shuffles handle at scale.

Diagram

flowchart LR
    D["Document"] --> S["Shingles"]
    S --> H["k hash functions"]
    H --> M["Keep minimum per hash"]
    M --> G["Signature of k values"]
    G --> B["Split into b bands of r rows"]
    B --> K["Hash each band to a bucket"]
    K --> C["Same bucket in any band: candidate"]
    C --> V["Verify with full signature"]

Worked example

A team building a language-model training corpus has 1 billion web documents and wants to drop near-duplicates with Jaccard similarity above 0.8 on word 5-gram shingles.

Signatures use k = 100 32-bit values: 400 bytes per document, 400 GB in total. With about 1,000 shingles per document, naive hashing is 10^14 hash evaluations, so the pass uses one-permutation hashing and runs on a few hundred cores for a few hours.

Banding with b = 20 bands of r = 5: the threshold is about (1/20)^(1/5) = 0.55. A pair at J = 0.8 becomes a candidate with probability 1 - (1 - 0.8^5)^20, about 0.9996. A pair at J = 0.3 becomes a candidate with probability 1 - (1 - 0.3^5)^20, about 0.047, and pairs below that almost never do. The job emits 20 billion (band hash, doc ID) rows, groups them by key in a shuffle, and generates candidate pairs within each bucket.

Verification compares full signatures and keeps pairs with estimated J >= 0.8; union-find forms duplicate clusters and one document per cluster is kept. The banding threshold sits well below 0.8, trading verification work for recall.

Hot buckets are the operational risk. Boilerplate-heavy pages, such as cookie banners or empty templates, can put millions of documents in one bucket, producing trillions of pairs. Cap bucket sizes and treat huge buckets as their own duplicate cluster or strip boilerplate before shingling.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
MinHash + LSHScales to billions, tunable threshold, mergeable signaturesOnly Jaccard on sets, needs good shinglingNear-duplicate detection on text or sets
SimHashOne 64-bit fingerprint, approximates cosineLess precise for moderate similarityWeb-scale exact or very-near duplicates
Exact hashing (SHA-256 of normalised text)Simple, exact, cheapMisses any edit at allRemoving byte-identical copies first
Embeddings + ANN indexCaptures meaning, paraphrasesExpensive, opaque, model driftSemantic similarity, not textual overlap
All-pairs exact JaccardExactQuadratic, infeasible beyond millionsSmall collections or final verification

Pitfalls in production

Leadership lens

Check yourself

  1. Why does the probability of equal minimum hashes equal the Jaccard similarity?

    Show answer

    A random hash orders the union uniformly, and the two minima are equal exactly when the first element of the union is in the intersection, which happens with probability intersection over union.

  2. With b bands of r rows, what happens to candidate pairs when you increase r and keep b fixed?

    Show answer

    Each band needs more agreeing values, so the S-curve shifts to a higher similarity threshold and becomes steeper; fewer low-similarity pairs are candidates, but recall near the threshold drops.

  3. Why is a 128-value signature enough no matter how long the documents are?

    Show answer

    The estimate's error depends only on k and the similarity, through sqrt(J(1 - J) / k), not on the size of the sets.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →