Vol. IX · Data Plate 4 of 12deduplication, near-duplicates, MinHash, locality-sensitive hashing, Jaccard similarity, shinglesDC

Deduplication.

Estimate how much two documents overlap from a few dozen hashes — and find all the similar pairs without checking every pair.

Duplicates waste compute and do worse than nothing: a string repeated hundreds of times is memorised (plate VIII.7), and a model trained on deduplicated data reaches the same quality in fewer steps and emits memorised text far less often. Lee and colleagues found a single 61-word sentence repeated 61 036 times in C4, a widely used dataset that had already been deduplicated at the level of whole sentences.

Exact duplicates are easy: hash each document and keep one per hash. Near-duplicates — the same article with a different date, a template with a few words changed — need a similarity measure. The standard one is the Jaccard similarity of the documents’ sets of word n-grams (“shingles”). MinHash estimates it from short signatures, and locality-sensitive hashing (LSH) groups signatures into bands so that only documents agreeing on a whole band are compared — finding similar pairs among billions of documents without comparing every pair.

Below: left, the probability that LSH flags a pair as candidates against their true Jaccard similarity, for the chosen bands and rows — an S-curve. Right, a test corpus of 40 passages and 40 edited copies: how many true pairs LSH finds, and how many false candidates it raises.

What you will learn
Workshop
Signatures of 64 MinHash values split into b bands of r rows (b × r ≤ 64). Left: probability that a pair becomes a candidate against its Jaccard similarity (3-word shingles). Right: 40 course passages plus one copy of each with the chosen share of words replaced; true pairs found and false candidates.

Similar pairs without comparing every pair

Copies with a tenth of their words replaced keep a Jaccard similarity of 0.58 with their originals on 3-word shingles, and the 64-value MinHash signatures estimate it as 0.58. With 16 bands of 4 rows, a pair becomes a candidate if it agrees on any one band; the S-curve’s threshold sits near 0.50, and the method finds 30 of the 40 copies; any false candidates (0 here) would be removed by an exact Jaccard check on each candidate pair. With 4 bands of 16 rows — a strict setting — the threshold rises to 0.92 and the method finds 0 of the 40 copies.

The work saved is the point. Comparing every pair of a billion documents means 5 × 10¹⁷ comparisons; LSH only compares documents that land in the same bucket for some band. The bands and rows set the trade-off between missed duplicates and wasted comparisons. The stakes are measurable: Lee and colleagues found a 61-word sequence repeated 61,036 times in C4, and that deduplication reduced how often trained models emitted memorised text while matching or improving their quality.

Deduplication can go too far. FineWeb found that deduplicating each crawl snapshot separately worked better than deduplicating across all snapshots at once, because global deduplication removed proportionally more of the higher-quality text that recurs across years.

Terms

Shingles
The set of overlapping word n-grams of a document.
Jaccard similarity
Size of the intersection of two sets over the size of their union.
MinHash
A signature whose entries agree between two documents with probability equal to their Jaccard similarity.
Locality-sensitive hashing
Bucketing signatures by bands so that only similar documents are likely to be compared.
MinHash estimates similarity from a short signature; LSH banding finds the similar pairs among billions without comparing every pair.

Sources

  1. Broder, “On the resemblance and containment of documents”, Compression and Complexity of Sequences, 1997 (MinHash).
  2. Lee et al., “Deduplicating Training Data Makes Language Models Better”, ACL 2022, arXiv:2107.06499.
  3. Leskovec, Rajaraman and Ullman, Mining of Massive Datasets, chapter 3 (banded LSH).