Deduplication & Near-Duplicate Detection

Why Deduplication Matters

In web crawling, search engines, and LLM pre-training datasets, duplicate content is everywhere:

• Re-syndicated news articles published across 500 websites.
• Near-identical product listings on e-commerce platforms.
• Identical code blocks copied across thousands of GitHub repositories.

IMPACTS OF UN-DEDUPLICATED DATA:
1. Data Leakage:      Exact training samples leak into validation and test sets!
2. Wasted Compute:    LLMs spend 30% of pre-training budget reading duplicate text!
3. Vector DB Waste:   Indexing 10 copies of the same article inflates RAM costs by 10x!

1. Exact Deduplication (Cryptographic Hashes)

For 100% exact bit-for-bit duplicate files:

Compute a cryptographic hash (for example MD5 or SHA-256) of each document file. Store hashes in a bloom filter or key value store. If a hash collision occurs, discard the duplicate document immediately.

Document A ──► [ SHA-256 ] ──► "a8f3b..."
Document B ──► [ SHA-256 ] ──► "a8f3b..." ──► Match Found! Discard Document B!

• Limitation: Fails completely if a single character, space, or comma differs between documents!

2. Near-Duplicate Text (MinHash + LSH)

For near-duplicate text (documents sharing 80% identical sentences):

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ STEP 1: SHINGLING        │ STEP 2: MINHASHING       │ STEP 3: LSH BUCKETING    │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Convert document into    │ Compress character sets  │ Hash signatures into     │
│ sets of overlapping      │ into compact numerical   │ buckets so similar       │
│ k-character shingles.    │ signature vectors.       │ documents collide in the │
│                          │ Preserves Jaccard Sim!   │ same bucket in O(1) time!│
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

Jaccard Similarity measures overlap between document shingle sets $A$ and $B$:

$$J(A, B) = \frac{|A \cap B|}{|A \cup B|}$$

Locality Sensitive Hashing (LSH) groups similar MinHash signatures into candidate buckets, finding near-duplicates across 100 million documents in minutes instead of days.

3. Near-Duplicate Images (Perceptual Hashing / pHash)

Standard cryptographic hashes change completely if an image is resized by 1 pixel.

Perceptual Hashing (pHash) converts images into frequency domain representations (using Discrete Cosine Transform):

• Resized, compressed, cropped, or recolored versions of an image produce nearly identical pHash bit strings.
• Distance between images is measured using Hamming Distance (counting differing bits).

Say this out loud

Deduplication removes exact and near duplicate content from datasets and catalogs. Exact duplicates are caught using SHA 256 cryptographic hashes. Near duplicate text is identified by estimating Jaccard similarity using MinHash and Locality Sensitive Hashing. Near duplicate images are detected using Perceptual Hashing and Hamming distance.

Followups to expect

1. How did deduplication improve LLaMA and RefinedWeb dataset quality? Deduplication using MinHash LSH removed over 30% of web crawl text, speeding up training while increasing downstream benchmark evaluation scores.
2. What is Semantic Deduplication using Vector Embeddings? Using dense vector cosine similarity (cosine sim $> 0.95$) to identify semantically identical sentences that express the exact same idea using different words.