Data Concepts

Deduplication at Scale

Exact duplicates are a hash lookup. Near-duplicates are the expensive ones, and the ones that straddle your split turn memorised text into a benchmark win.

Each document collapses to a short signature, the signature splits into bands, and only documents colliding in at least one band ever get compared to each other

Why Does This Exist?

Exact duplicates are solved. Hash the content, group by the hash, keep one. Linear time, no tuning.

Near-duplicates are the expensive ones, and they inflate every benchmark you report — because one straddling your train/test split turns memorisation into what looks like generalisation. The same paragraph with a changed date, a boilerplate footer, one reworded sentence. None of those share a hash.

Then the wall. Checking every pair means $n(n-1)/2$ comparisons, so 10 million documents is roughly $5 \times 10^{13}$ of them. At a microsecond each that's a year and a half of CPU time for one pass. Everything below exists to get around that number.

Think of It Like This

A sorting office, not a reading room

Ten million letters, and you need the ones addressed to the same house. Comparing every letter to every other one is the reading-room approach, and you'd still be at it next year.

A sorting office does something else. It reads the postcode, throws the letter in the matching pigeonhole, and never compares anything to anything. Two letters for the same house land in the same hole. Then a human reads one hole at a time.

The clever part is several partial postcodes at once. A smudged digit knocks a letter out of one pigeonhole, but it still lands in the other three, so a near match gets found anyway. You never eliminate the reading. You shrink it to whatever sits inside the holes.

How It Actually Works

Exact first, and normalise before you hash

Hash each document's content and group. Normalise first though: trim whitespace, fold case, normalise Unicode, strip boilerplate headers. Two identical articles differing by a trailing newline hash differently, so cleaning runs ahead of this or the duplicates stay invisible and your dedupe pass reports success.

Shingles, Jaccard, MinHash

Break each document into overlapping k-grams, called shingles. "the cat sat" at $k = 3$ gives "the", "he ", "e c" and so on. A document becomes a set, and overlap becomes the question.

Jaccard similarity is what you want: intersection size over union size. Right target, wrong thing to compute, since holding full shingle sets for 10 million documents is enormous and intersecting them pairwise is the wall again.

MinHash estimates Jaccard from a small fixed-size signature. One sentence carries it: hash every shingle, keep only the minimum, and the probability two documents' minimums agree is exactly their Jaccard similarity. One hash function gives a coin flip weighted by the answer. Use 128, count the agreements, and you have an estimate. Megabytes become 128 numbers.

Banding, and why it beats the quadratic

A 128-row signature still leaves every pair to compare. Locality-sensitive hashing removes that. Split the rows into $b$ bands of $r$ rows, hash each band to a bucket, and only compare documents sharing a bucket in at least one band. Similarity search becomes candidate generation.

Two documents agreeing on most rows will agree on some whole band with high probability. Two unrelated ones almost certainly won't. The chance a pair becomes a candidate at Jaccard $s$ is $1 - (1 - s^r)^b$ , an S-curve whose knee sits near $(1/b)^{1/r}$ .

That's a dial, not a setting. More bands of fewer rows: lower knee, higher recall, a much larger pile of candidates to verify exactly. Fewer bands of more rows: fewer candidates, silently missed pairs.

The other regimes

SimHash suits very short text, where shingle sets get too small for MinHash. For semantic duplicates sharing no tokens, two write-ups of one event in different words, you need embeddings with an approximate-nearest-neighbour index and cosine distance. Images use perceptual hashing, which survives resizing and re-encoding.

What to do once you've found them

Three defensible choices: keep one arbitrarily, keep the highest-quality one by whatever signal you already compute, or keep a count as a sample weight, which preserves that this text is genuinely common.

For LLM pretraining the payoff is measurable: better quality per token, and the models memorise less verbatim training text.

Worked example

"the cat sat" and "the cat sit". At $k = 3$ each gives 9 shingles.

They share "the", "he ", "e c", " ca", "cat", "at " and "t s", so the intersection is 7. The first adds " sa" and "sat", the second " si" and "sit". Union is $9 + 9 - 7 = 11$ , so Jaccard is $7/11 = 0.636$ .

A 128-row signature should therefore agree on about $128 \times 0.636 = 81$ rows. Now band it. At 16 bands of 8 rows the knee is $(1/16)^{1/8} = 0.707$ , above this pair, and the candidate probability lands at 0.35, so you'd miss it two times in three. At 32 bands of 4 rows the knee drops to 0.420 and the pair gets caught essentially always. Same 128 numbers, opposite outcome, and far more candidates to verify.

Show Me the Code

1import numpy as np2
3def shingles(text: str, k: int = 3) -> set[str]:4    return {text[i : i + k] for i in range(len(text) - k + 1)}5
6def candidate_prob(s: float, bands: int, rows: int) -> float:7    return float(1 - (1 - s**rows) ** bands)          # the LSH S-curve8
9a: set[str] = shingles("the cat sat")10b: set[str] = shingles("the cat sit")11jaccard: float = len(a & b) / len(a | b)12
13print(len(a), len(b), len(a & b), len(a | b))          # -> 9 9 7 1114print(round(jaccard, 4))                               # -> 0.636415print(int(np.round(128 * jaccard)))                    # -> 81   signature rows expected to agree16print(round(candidate_prob(jaccard, 16, 8), 2))        # -> 0.35 wide bands miss this pair17print(round(candidate_prob(jaccard, 32, 4), 2))        # -> 1.0  narrow bands catch it

The last two lines are the whole engineering decision, and the documents didn't change.

Watch Out For

Deduplicating after the split, or not at all

You split first out of habit, then dedupe each side separately, or skip it because the corpus "came clean". Either way, near-duplicates straddle the boundary.

Your benchmark now measures recall of memorised text. A model scores 0.91 on a held-out set whose rows it already read in slightly different words, and nothing in the training run tells you. It's data leakage with a similarity threshold instead of a shared column.

Dedupe the corpus before splitting, then run a decontamination pass against the evaluation sets you plan to report. See dataset decontamination.

Treating dedupe as free deletion

Contract clauses are near-identical by design. Templated support replies are meant to be templated. Product listings in one category differ by three fields. Aggressive removal there destroys real distribution mass.

Set a Jaccard threshold of 0.8 across a support corpus and you can lose most of one intent class, because every example of it was templated. The class doesn't vanish from your data dictionary, only from your training set, and the model quietly stops handling it.

Log removals per source and class before committing to a threshold. A class losing 90% of its rows is a finding, not a cleanup. Prefer weights over deletion when the repetition is real.

The Quick Version

Exact duplicates are a hash lookup after normalisation. Normalise first or they stay invisible.
Near-duplicates are the expensive case. They inflate benchmarks by turning memorisation into apparent generalisation.
All-pairs comparison is quadratic: 10 million documents is about $5 \times 10^{13}$ pairs, so it never happens.
Shingling turns a document into overlapping k-grams. Jaccard is the target measure.
MinHash estimates Jaccard from a small signature, because the chance two minimum hashes agree equals Jaccard.
LSH bands the signature and compares only band-colliding pairs, turning search into candidate generation.
More bands of fewer rows means higher recall and more candidates. The knee sits near $(1/b)^{1/r}$ .
SimHash for short text, embeddings plus an ANN index for semantic duplicates, perceptual hashing for images.
Keep one, keep the best, or keep a count as a weight. In pretraining, dedupe raises quality per token.
Aggressive removal on repetitive data deletes real distribution mass. Log removals per class first.