MinHash Deduplication

MinHash provides a unbiased estimator of the Jaccard similarity coefficient between two sets. By comparing the minimum hash values of shingled documents, the algorithm approximates the ratio of the intersection to the union of their n-gram sets without requiring an expensive pairwise comparison of all elements. This statistical property allows for sub-linear deduplication in massive corpora like Common Crawl.

Before hashing, documents are decomposed into k-shingles—contiguous subsequences of tokens of a fixed length k. For text, k is typically 5 to 9 words. This process converts a document into a set of features that is robust to minor edits, reordering, and paraphrasing. The choice of k directly impacts the granularity of duplicate detection:

• Low k (3-4): Catches small phrase overlaps, higher false positives
• High k (8-10): Identifies larger structural copies, higher precision

To avoid O(n²) comparisons, MinHash signatures are split into b bands of r rows each. Documents that hash to the same bucket in any band are considered candidate pairs. This Locality-Sensitive Hashing (LSH) technique probabilistically guarantees that similar documents collide with high probability while dissimilar ones are pruned. The parameters b and r are tuned to control the similarity threshold, creating an adjustable precision-recall curve for deduplication sensitivity.

MinHash deduplication is a critical pre-processing defense against synthetic data contamination and model autophagy. By removing near-duplicate documents from training corpora, it prevents models from memorizing and regurgitating verbatim passages, which accelerates tail erosion and reduces output diversity. Research has shown that deduplicating web-scale datasets with MinHash significantly improves perplexity and reduces the frequency of exact training data extraction attacks.

While both are LSH techniques, they serve distinct purposes:

• MinHash: Estimates Jaccard similarity; ideal for near-duplicate document detection and corpus deduplication.
• SimHash: Estimates cosine similarity via randomized rounding; optimized for identifying exact or near-exact duplicates in web crawling. MinHash is preferred for training corpus sanitization because it is more robust to paraphrasing and document restructuring, catching semantic duplicates that SimHash would miss.

Production deduplication pipelines typically execute MinHash in a MapReduce or Spark job across distributed clusters. The workflow involves:

1. Shingling: Convert each document to a set of n-grams
2. MinHashing: Apply multiple hash functions to generate a compact signature
3. LSH Bucketing: Group signatures into candidate pairs
4. Thresholding: Filter pairs above a Jaccard similarity cutoff (commonly 0.8) This process can deduplicate petabytes of text, such as the Colossal Clean Crawled Corpus (C4), reducing storage and preventing memorization.