Deduplication › Deduplication at Scale

The naive near-duplicate detection algorithm is $O(N^2)$ in the number of documents, which is completely infeasible for web-scale corpora. Industrial deduplication pipelines use a combination of techniques to scale to billions of documents.

MinHash is the key technique that makes near-duplicate detection tractable at scale. Rather than computing Jaccard similarity directly between all pairs of documents, you compute a compact signature (a MinHash signature) for each document. Two documents with similar signatures are likely near-duplicates, and you only need to compare those candidate pairs.

The theoretical foundation of MinHash rests on a remarkable probabilistic guarantee. For any single hash function $h$ drawn from a min-wise independent family, and for any two sets $A$ and $B$:

$$P\!\left(\min_{x \in A} h(x) = \min_{x \in B} h(x)\right) = J(A, B)$$

where:

• $\min_{x \in A} h(x)$: the minimum hash value obtained by applying $h$ to every element of set $A$
• $J(A, B)$: the Jaccard similarity of the two sets
• The probability is taken over random draws of the hash function $h$

This identity says that the probability of the two sets having the same minimum hash value exactly equals their Jaccard similarity. The proof follows from the definition of Jaccard similarity: if we think of the union $A \cup B$ as a pool of shingles and apply a random hash function that assigns each shingle a unique random rank, then the minimum-ranked shingle in the pool is equally likely to come from $A$, from $B$, or from $A \cap B$. The minimum-ranked shingle comes from $A \cap B$ if and only if the minimums of $A$ and $B$ are equal, and the probability of that happening is $|A \cap B| / |A \cup B| = J(A, B)$.

By using $m$ independent hash functions and computing $m$ minimum hash values per document, you obtain a MinHash signature of length $m$ that is an unbiased estimator of Jaccard similarity. The estimation variance decreases as $m$ increases; in practice, $m = 128$ or $m = 256$ provides good accuracy with manageable signature size.

We cover MinHash in full mathematical detail in the next chapter, including Locality-Sensitive Hashing (LSH), which groups documents by their signature into buckets to avoid exhaustive pairwise comparison. The combination of MinHash signatures and LSH bucketing reduces the deduplication problem from $O(N^2)$ comparisons to a manageable number of comparisons within each bucket, making billion-document deduplication computationally feasible.

Once you have identified which pairs of documents are near-duplicates, you need to decide which member of each cluster to keep. The standard data structure for this is union-find (also called disjoint set union, or DSU).

Union-find maintains a forest of trees where each tree represents a cluster of near-duplicate documents. The algorithm proceeds in three phases. First, initialization assigns each document to its own singleton cluster by setting $\text{parent}[d] = d$ for all documents $d$. Second, for each near-duplicate pair $(d_i, d_j)$ identified by the MinHash LSH step, you merge their clusters with the union(d_i, d_j) operation. Third, after processing all pairs, each tree in the forest contains all near-duplicates of a given document, and you keep one representative from each tree.

The representative selection step is where quality information enters the picture. If you have a quality score for each document (based on source domain, length, readability, or other signals), you select the highest-scoring member of each cluster as the representative and discard the rest. Without quality scores, you typically keep the first document added to the cluster, which is equivalent to greedy deduplication.

Union-find with path compression and union by rank runs in nearly $O(N \alpha(N))$ time, where $\alpha$ is the inverse Ackermann function. For practical purposes, $\alpha(N) \leq 5$ for any $N$ representable in the universe, so the algorithm runs in effectively linear time. This efficiency is important because, after MinHash LSH produces millions of near-duplicate pairs, you need to process all those pairs efficiently to identify the actual clusters.

For trillion-token corpora, even the MinHash plus LSH approach requires distributed computing. The standard architecture uses a MapReduce or Apache Spark pipeline organized around three phases.

The map phase assigns each document a set of LSH bucket identifiers based on its MinHash signature. A document's MinHash signature is divided into $b$ bands of $r$ hash values each ($m = b \times r$). Two documents that share all $r$ hash values in any single band are placed into the same bucket for that band. The probability that two documents with Jaccard similarity $s$ end up in the same bucket for at least one band is $1 - (1 - s^r)^b$, and the parameters $b$ and $r$ can be tuned to achieve a desired false-positive and false-negative rate.

The shuffle phase, handled by the distributed computing framework, collects all documents assigned to each bucket. Since each document may be assigned to multiple buckets (one per band), this step can involve significant data movement. The total number of bucket assignments per document is $b$, so the total data moved is $O(b \times N)$ where $N$ is the number of documents.

The reduce phase performs exact Jaccard similarity computation within each bucket on the small subset of documents that share a bucket. Because LSH guarantees that only documents with sufficiently similar signatures end up in the same bucket, these within-bucket comparisons are vastly fewer than the $O(N^2)$ comparisons that naive pairwise matching would require. The reduce phase also applies union-find to merge near-duplicate pairs into clusters and select representatives.

The BigScience workshop, which produced the BLOOM language model, published their deduplication pipeline for the 341 billion token ROOTS corpus as part of a broader data transparency effort. EleutherAI's deduplication of the Common Crawl for the Pile used distributed MinHash LSH and removed roughly 30% of the initial corpus before further filtering. The Dolma dataset, produced by the Allen Institute for AI, applied MinHash deduplication across each of its component sources independently, then applied a cross-source deduplication pass to remove documents that appeared in both web crawl data and more curated sources like Wikipedia.

Large-scale models increasingly use retrieval-augmented generation (RAG) architectures or are trained with long context windows that span multiple retrieved passages. For these use cases, deduplication at the passage level becomes relevant in addition to document-level deduplication.

Passage-level deduplication uses the same MinHash approach but applied to fixed-length chunks (typically 256 to 512 tokens) rather than entire documents. A document might be unique at the document level but contain several passages that appear verbatim in many other documents. Removing those repeated passages requires either suffix array methods or passage-level MinHash applied across all fixed-size chunks in the corpus.

The challenge with passage-level deduplication is boundary sensitivity. Whether a chunk falls exactly on a sentence boundary or cuts through a sentence in the middle can significantly affect its shingle set, potentially causing two identical passages to have different shingle sets because their chunk boundaries fell differently. Handling this correctly requires either sentence-boundary-aware chunking or overlapping chunks with stride less than chunk size, so that any sentence appears fully within at least one chunk regardless of how the chunking was applied.