near-duplicate detection

**Near-duplicate detection** identifies documents or text passages that are highly similar but not exactly identical — such as content that has been **slightly edited, reformatted, paraphrased, or scraped from different versions** of the same source. It is essential for dataset quality because exact deduplication misses these variants. **Why Near-Duplicates Are Problematic** - **Web Scraping**: The same article appears on multiple sites with minor formatting differences, author attribution changes, or added boilerplate. - **Syndicated Content**: News articles distributed through wire services appear on hundreds of sites with minor local edits. - **Template Content**: Auto-generated pages (product listings, weather reports) share structure with only small data differences. - **Version History**: Edited documents, code revisions, or wiki edit histories produce near-duplicate pairs. **Detection Methods** - **MinHash**: Create multiple hash signatures from character or word n-grams using random hash functions. Documents with similar content produce similar signatures. Compare signatures using **Jaccard similarity** — pairs above a threshold (typically 0.8) are near-duplicates. - **LSH (Locality-Sensitive Hashing)**: Bucket MinHash signatures so that similar documents are likely to hash to the **same bucket**, enabling efficient O(N) approximate search instead of O(N²) pairwise comparison. - **SimHash**: Produce a single binary hash per document. Near-duplicates produce hashes with few differing bits (small **Hamming distance**). - **Embedding Similarity**: Encode documents with a neural model and find pairs with high **cosine similarity**. - **N-Gram Overlap**: Compute the fraction of shared n-grams between document pairs. **Industry Tools** - **datasketch**: Python library implementing MinHash + LSH. - **Dedup**: Google's deduplication pipeline used for C4 and other datasets. - **text-dedup**: Unified library supporting multiple near-duplicate detection algorithms. Near-duplicate detection is a **standard preprocessing step** for large language model training — removing near-duplicates from Common Crawl-based datasets can eliminate **20–40%** of content.