MinHash and Locality-Sensitive Hashing

"I compared every document to every other document. Halfway through the second trillion comparisons, I began to suspect there was a better way."

A Reducer That Counted Too High

Earlier sections of this chapter computed exact answers: an exact word count, an exact sort, an exact join. This section confronts a problem where the exact answer is the obstacle rather than the goal. Suppose you hold a billion documents and you want every pair that is "almost the same" so you can drop the redundant copies. The exact formulation, compare all pairs and keep the similar ones, requires on the order of $N^2 / 2$ comparisons. For a billion documents that is roughly $5 \times 10^{17}$ comparisons, and no cluster of any size makes that tractable. The way out is to stop insisting on examining every pair, and instead arrange the computation so that dissimilar pairs are never compared at all. That arrangement is the subject of this section, and it is the first place in the book where we trade an exact computation for a probabilistic one to make scale possible, a trade that Section 6.8 generalizes into a whole toolkit of approximate algorithms.

1. Why Deduplication Decides Model Quality Beginner

A web crawl is full of repetition. The same news article appears on hundreds of syndicating sites, boilerplate headers and footers recur across every page of a domain, and scraped forums echo the same answer in thread after thread. If this redundancy is fed verbatim into a pretraining corpus, the model sees some passages thousands of times more often than others, which wastes compute, inflates the apparent size of the dataset, encourages memorization of the over-represented text, and can leak benchmark questions that happen to be duplicated across the web. Removing near-duplicates, not just exact duplicates, measurably improves the resulting model and reduces the tokens needed to train it. Clean data is not a luxury applied after the interesting work; at corpus scale it is the interesting work, and it is why a data-processing chapter sits early in a book about training large models. The downstream payoff is developed when we reach foundation-model data pipelines in Chapter 19.

The unit of comparison is a document represented as a set. The standard construction is to slide a window of $k$ consecutive words (or characters) across the text and collect the resulting shingles, so that "the distributed system scaled out" with $k = 3$ becomes the set {"the distributed system", "distributed system scaled", "system scaled out"}. Two documents that share most of their shingles are near-duplicates; two that share few are unrelated. The natural measure of set overlap is the Jaccard similarity, and everything in this section is built to estimate it cheaply and to find high-Jaccard pairs without examining all pairs.

2. Jaccard Similarity and the MinHash Estimator Intermediate

Let document $A$ and document $B$ be sets of shingles. Their Jaccard similarity is the size of their intersection over the size of their union,

This is exactly the quantity we want, and computing it directly for one pair is easy. The trouble is that storing the full shingle set of every document is expensive, and comparing all pairs of sets is the quadratic cost we are trying to avoid. MinHash attacks both problems at once by replacing each set with a short fixed-length signature whose agreement rate estimates $J$ directly.

Pick a random permutation $\pi$ of the universe of all possible shingles, and define $h(A) = \min_{x \in A} \pi(x)$, the smallest rank that any element of $A$ receives under $\pi$. The defining property of this min-hash is that the element achieving the minimum over the union $A \cup B$ is equally likely to be any element of the union, and the hashes of $A$ and $B$ agree exactly when that minimizing element lies in the intersection. Therefore

A single min-hash is a coin whose probability of heads is precisely the Jaccard similarity. Using $n$ independent permutations gives a signature of $n$ min-hashes per document, and the fraction of the $n$ positions where the two signatures agree is an unbiased estimator of $J$. Because the positions are independent, the estimator's variance is $J(1 - J)/n$, so the error shrinks like $1/\sqrt{n}$: quadruple the signature length and you halve the typical error. A signature of a few hundred integers stands in for a shingle set of any size, which is the compression that makes the whole pipeline fit in memory and in the shuffle.

The code below makes both claims concrete. It builds two near-duplicate documents, computes their true Jaccard exactly, then estimates it from MinHash signatures of growing length, repeating each length two hundred times so the shrinking spread of the estimator is visible. It then runs the LSH banding stage that the next section explains, finding near-duplicate candidate pairs in a small corpus.

import numpy as np

def shingles(text, k=3):                       # set of k-word windows
    words = text.split()
    return {" ".join(words[i:i + k]) for i in range(len(words) - k + 1)}

doc_a = ("the distributed system scaled out across many machines and kept "
         "every worker busy processing its own shard of the training corpus")
doc_b = ("the distributed system scaled out across several machines and kept "
         "each worker busy processing its own shard of the training corpus")

A, B = shingles(doc_a), shingles(doc_b)
true_jaccard = len(A & B) / len(A | B)          # exact Jaccard, for reference

rng = np.random.default_rng(7)
universe = sorted(A | B)
idx = {s: i for i, s in enumerate(universe)}
P = 2_147_483_647                              # a large prime modulus

def make_hashes(n):                            # n random hash functions a*x+b mod P
    return rng.integers(1, P, size=n), rng.integers(0, P, size=n)

def signature(members, a, b):                  # MinHash: min over the set per hash
    rows = np.array([idx[s] for s in members])
    return ((np.outer(a, rows) + b[:, None]) % P).min(axis=1)

print("true Jaccard            :", f"{true_jaccard:.4f}")
print(" sig length |  mean MinHash est |  est std dev (across 200 trials)")
for n in [16, 64, 256, 1024, 4096]:
    ests = []
    for _ in range(200):                       # repeat to expose shrinking variance
        a, b = make_hashes(n)
        ests.append(np.mean(signature(A, a, b) == signature(B, a, b)))
    ests = np.array(ests)
    print(f"  {n:>6d}    |      {ests.mean():.4f}       |          {ests.std():.4f}")

true Jaccard            : 0.5200
 sig length |  mean MinHash est |  est std dev (across 200 trials)
 -----------|-------------------|---------------------------------
      16    |      0.5184       |          0.1323
      64    |      0.5259       |          0.0650
     256    |      0.5245       |          0.0322
    1024    |      0.5213       |          0.0164
    4096    |      0.5211       |          0.0077

The mean column never drifts from the true value of $0.52$, which is what "unbiased" means: more positions do not move the target, they only tighten the spread around it. The standard deviation falls from $0.13$ at sixteen hashes to $0.008$ at four thousand, a clean halving for every quadrupling, exactly as the variance formula promises. A signature of a few hundred integers already estimates Jaccard to within a few percent, and it does so in a fixed amount of space no matter how long the documents are.

3. LSH Banding: Finding Candidates Without Comparing All Pairs Advanced

MinHash shrinks each document to a short signature, but comparing all pairs of signatures is still quadratic. Locality-Sensitive Hashing removes the quadratic step by hashing signatures so that similar ones collide and dissimilar ones almost never do. Split each signature of length $n$ into $b$ bands of $r$ rows, so $n = b \cdot r$. For each band, hash the $r$ values in that band to a bucket; two documents land in the same bucket for a given band only if all $r$ of their values in that band are identical. Two documents become a candidate pair if they share a bucket in at least one band.

The probability analysis is what makes this work as a tunable filter. For two documents with Jaccard $s$, each row matches with probability $s$, so an entire band of $r$ rows matches with probability $s^r$, a band fails to match with probability $1 - s^r$, all $b$ bands fail with probability $(1 - s^r)^b$, and therefore the pair becomes a candidate with probability

As a function of $s$ this is an S-curve with a sharp threshold near $s \approx (1/b)^{1/r}$. Below the threshold the candidate probability is almost zero, above it almost one. By choosing $b$ and $r$ you place the threshold exactly where you want the line between "near-duplicate" and "unrelated" to fall. A common choice for aggressive deduplication is to put the threshold around $0.8$, so that only genuinely redundant documents survive the filter while unrelated pairs are discarded before any direct comparison happens.

Expressed as MapReduce, the banding stage is the most natural job imaginable. The map function takes a document, computes its signature, and emits one key-value pair per band, where the key is the (band index, band hash) and the value is the document id. The shuffle groups by that key, so every bucket arrives at a reducer with the list of documents that fell into it. The reduce function emits a candidate pair for each pair of documents in a bucket, optionally verifying the true similarity before keeping it. This is the same map, shuffle, reduce skeleton from Section 6.2, with band keys playing the role that words played in word count.

# continued from Code 6.7.1; builds a small corpus and runs the LSH banding job
from collections import defaultdict

base = ("machine learning models trained on web scale text corpora require "
        "careful deduplication of the pretraining data before any training begins")
syn = {"careful": "thorough", "require": "need", "begins": "starts",
       "models": "networks", "trained": "fitted"}

def variant(text, swaps):                      # make a controlled near-duplicate
    out, done = [], 0
    for w in text.split():
        if done < swaps and w in syn:
            out.append(syn[w]); done += 1
        else:
            out.append(w)
    return " ".join(out)

corpus = {"doc0": base, "doc1": variant(base, 1), "doc2": variant(base, 2),
          "doc3": "completely unrelated content about gardening tomatoes in summer heat",
          "doc4": base + " and it must be reproducible"}

n_hashes, bands = 128, 32                       # 32 bands of 4 rows
rows = n_hashes // bands
a128, b128 = make_hashes(n_hashes)
gshingles = sorted(set().union(*(shingles(t) for t in corpus.values())))
gidx = {s: i for i, s in enumerate(gshingles)}

def sig128(text):
    r = np.array([gidx[s] for s in shingles(text)])
    return ((np.outer(a128, r) + b128[:, None]) % P).min(axis=1)

sigs = {d: sig128(t) for d, t in corpus.items()}

buckets = defaultdict(list)                      # MAP + SHUFFLE: emit (band, hash) keys
for d, s in sigs.items():
    for band in range(bands):
        chunk = tuple(s[band * rows:(band + 1) * rows].tolist())
        buckets[(band, hash(chunk))].append(d)

candidates = set()                               # REDUCE: pairs sharing any bucket
for members in buckets.values():
    for i in range(len(members)):
        for j in range(i + 1, len(members)):
            candidates.add(tuple(sorted((members[i], members[j]))))

print("LSH candidate near-duplicate pairs (128 rows, 32 bands of 4):")
for pa, pb in sorted(candidates):
    sa, sb = shingles(corpus[pa]), shingles(corpus[pb])
    print(f"   {pa} ~ {pb}   true Jaccard = {len(sa & sb) / len(sa | sb):.3f}")

LSH candidate near-duplicate pairs (128 rows, 32 bands of 4):
   doc0 ~ doc1   true Jaccard = 0.714
   doc0 ~ doc2   true Jaccard = 0.636
   doc0 ~ doc4   true Jaccard = 0.783
   doc1 ~ doc2   true Jaccard = 0.714
   doc1 ~ doc4   true Jaccard = 0.577
   doc2 ~ doc4   true Jaccard = 0.519

The output recovers exactly the near-duplicate pairs among the four variants of the base document and produces nothing for the unrelated doc3, which never shared a band with anything. On five documents the saving is invisible, but the structure is the point: the number of (band, hash) keys emitted is linear in the number of documents, the shuffle groups them, and the only comparisons performed are inside buckets that already collided. Scale the corpus to a billion documents and the candidate set stays proportional to the number of genuinely similar pairs rather than to $N^2$. Figure 6.7.1 traces this flow from documents through signatures and bands into buckets, and the reduce arrow back to candidate pairs is the only place a direct comparison ever happens.

from datasketch import MinHash, MinHashLSH

def make_minhash(text, num_perm=128):
    m = MinHash(num_perm=num_perm)
    for sh in shingles(text):                  # same shingles as above
        m.update(sh.encode("utf8"))
    return m

lsh = MinHashLSH(threshold=0.6, num_perm=128)  # picks b and r to hit the threshold
mh = {d: make_minhash(t) for d, t in corpus.items()}
for d, m in mh.items():
    lsh.insert(d, m)

print(lsh.query(mh["doc0"]))                   # near-duplicates of doc0, no all-pairs scan

4. The Same Banding Returns as Vector Search Intermediate

The banding idea you just built for set similarity is one instance of a general principle: design a hash family that makes nearby points collide, and you turn nearest-neighbor search into a bucket lookup. MinHash is the locality-sensitive family for Jaccard distance over sets. Other distances have their own families, for example random-projection hashing for cosine and Euclidean distance over dense vectors, but the LSH banding mechanism is identical, group by hash, compare only within buckets. This is why the algorithm reappears far from data cleaning.

When a retrieval system must find the embedding vectors closest to a query among billions of stored vectors, the exact search is again quadratic and again avoided by approximate nearest-neighbor methods, of which LSH is the conceptual ancestor. We meet approximate nearest-neighbor search as a tool for classical models in Chapter 12, and as the indexing engine of distributed vector databases in Chapter 25. The banding you implemented in Code 6.7.2 and the bucket lookup in Code 6.7.3 are the same shape as the index probe inside a vector database; only the hash family and the distance change.

5. Where the Approximation Bites Intermediate

Because the method is probabilistic, it makes two kinds of error, and an honest pipeline budgets for both. A false negative is a near-duplicate pair that never shares a bucket, possible because every one of its bands happened to differ; its probability is $(1 - s^r)^b$, small for high-similarity pairs but never exactly zero. A false positive is an unrelated pair that collides in some band by chance and enters the candidate set; the reduce stage controls these cheaply by recomputing the true Jaccard on each candidate and discarding the ones below threshold, since the candidate set is small. The tuning knobs $b$ and $r$ trade these errors against each other and against cost: more bands raise recall and the candidate count, longer bands raise precision and the false-negative rate. The S-curve of Section 3 is the design tool, and the communication cost of the shuffle, which carries $b$ keys per document, is the budget it is tuned against, the kind of cost model developed in Chapter 3.

There is also a data-skew hazard specific to the shuffle. A boilerplate fragment shared by millions of documents produces a single enormous bucket, and the reducer that receives it faces a near-quadratic blowup inside that one bucket, the straggler problem this chapter keeps returning to. Practical systems cap bucket sizes, sample within giant buckets, or strip common boilerplate before shingling. The lesson is that the algorithm removes the global quadratic but can reintroduce a local one through skew, which is exactly the shuffle-skew problem that Chapter 7 treats in depth for Spark.

You now have a method that replaces a quadratic similarity join with two linear MapReduce passes, the probability theory that explains why MinHash signatures estimate Jaccard and why LSH banding finds the right candidates, and the cost and skew caveats that keep it honest. This is the first deliberately approximate algorithm in the book, and it opens a door. The next section widens it, building a family of small-space sketches, counting distinct items with HyperLogLog and frequencies with count-min, that answer otherwise impossible questions over streams and corpora. That family continues in Section 6.8.