Near-duplicate detection with MinHash LSH

Deep dive

How it works

Parts:

• shingler — turns an item into a set of hashed n-grams
• signature — k minima of k universal hashes per item
• band table — b buckets keyed by r signature rows
• verifier — estimated or exact Jaccard on candidate pairs
• union-find — merges verified pairs into clusters

1. Normalize (lowercase, collapse whitespace, optionally strip punctuation) and shingle: the set of hashed word 5-grams (character 5-9-grams for short or non-space-separated text).
2. Sign. For i = 1..k: sig[i] = min over shingles x of h_i(x), with h_i(x) = (a_i·x + b_i) mod p, p = 2⁶¹ − 1, random a_i ≠ 0, b_i.
3. Band. Split sig into b bands of r values. Key = hash of (band index, r values). Insert the doc id into buckets[key].
4. Candidates. Every pair sharing any bucket. Optionally verify by estimated Jaccard (signature agreement) or exact Jaccard on the shingle sets.
5. Cluster with union-find over verified pairs. Keep one document per cluster (the longest, the earliest, the highest quality score).

P(candidate | similarity s), b=20 r=5:
 s:   0.2    0.4    0.5    0.6    0.7    0.8    0.9
 P:   0.006  0.186  0.470  0.802  0.975  1.000  1.000

Raising r sharpens and moves the threshold up. Raising b moves it down. Pick (b, r) so the false-negative rate at your target similarity is acceptable, then verify to drop false positives.

Code

use std::collections::HashMap;

const P: u64 = (1 << 61) - 1;                               // Mersenne prime: cheap mod

fn mulmod(a: u64, b: u64) -> u64 {
    let x = (a as u128) * (b as u128);
    let r = ((x & P as u128) + (x >> 61)) as u64;             // fold: 2^61 ≡ 1 (mod P)
    if r >= P { r - P } else { r }
}

fn splitmix(mut z: u64) -> u64 {
    z = z.wrapping_add(0x9E3779B97F4A7C15);
    z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
    z ^ (z >> 31)
}

/// Hashed word n-grams of a lowercased, whitespace-normalized document.
fn shingles(doc: &str, n: usize) -> Vec<u64> {
    let words: Vec<String> = doc.split_whitespace().map(|w| w.to_lowercase()).collect();
    let mut out: Vec<u64> = words.windows(n.min(words.len()).max(1)).map(|g| {
        g.iter().fold(0xcbf29ce484222325u64, |h, w| {          // FNV-1a over the n-gram
            w.bytes().chain([b' ']).fold(h, |h, b| (h ^ b as u64).wrapping_mul(0x100000001b3))
        }) % P
    }).collect();
    out.sort_unstable(); out.dedup();
    out
}

pub struct MinHasher { a: Vec<u64>, b: Vec<u64> }
impl MinHasher {
    pub fn new(k: usize, seed: u64) -> Self {
        let a = (0..k).map(|i| splitmix(seed + 2 * i as u64) % (P - 1) + 1).collect();
        let b = (0..k).map(|i| splitmix(seed + 2 * i as u64 + 1) % P).collect();
        MinHasher { a, b }
    }
    pub fn sign(&self, sh: &[u64]) -> Vec<u64> {
        let mut sig = vec![u64::MAX; self.a.len()];
        for &x in sh {
            for i in 0..sig.len() {
                let h = mulmod(self.a[i], x) + self.b[i];
                let h = if h >= P { h - P } else { h };
                if h < sig[i] { sig[i] = h; }
            }
        }
        sig
    }
}

fn find(p: &mut Vec<usize>, mut x: usize) -> usize {
    while p[x] != x { p[x] = p[p[x]]; x = p[x]; }               // path halving
    x
}

/// Cluster ids per document; pairs must share a band AND have estimated Jaccard >= thresh.
pub fn dedup(sigs: &[Vec<u64>], bands: usize, rows: usize, thresh: f64) -> Vec<usize> {
    let mut parent: Vec<usize> = (0..sigs.len()).collect();
    for band in 0..bands {
        let mut buckets: HashMap<&[u64], Vec<usize>> = HashMap::new();  // one map per band
        for (d, s) in sigs.iter().enumerate() {
            buckets.entry(&s[band * rows..(band + 1) * rows]).or_default().push(d);
        }
        for docs in buckets.values().filter(|v| v.len() > 1) {
            for &other in &docs[1..] {
                let (x, y) = (&sigs[docs[0]], &sigs[other]);
                let est = x.iter().zip(y).filter(|(a, b)| a == b).count() as f64 / x.len() as f64;
                if est >= thresh {
                    let (ra, rb) = (find(&mut parent, docs[0]), find(&mut parent, other));
                    parent[ra] = rb;
                }
            }
        }
    }
    (0..sigs.len()).map(|d| find(&mut parent, d)).collect()
}

fn main() {
    let base = "the quick brown fox jumps over the lazy dog while the cat sleeps on the warm mat near the \
                door and the old clock in the hall ticks slowly as rain falls on the roof of the quiet house";
    let docs = [
        base.to_string(),
        base.replace("warm", "soft"),                            // near duplicate
        base.to_uppercase(),                                     // same after normalization
        "an entirely different text about minhash signatures and locality sensitive hashing buckets".into(),
    ];
    let mh = MinHasher::new(100, 42);
    let sigs: Vec<Vec<u64>> = docs.iter().map(|d| mh.sign(&shingles(d, 5))).collect();
    let (s0, s1) = (shingles(&docs[0], 5), shingles(&docs[1], 5));
    let inter = s0.iter().filter(|x| s1.binary_search(x).is_ok()).count();
    let est = sigs[0].iter().zip(&sigs[1]).filter(|(a, b)| a == b).count() as f64 / 100.0;
    println!("true Jaccard {:.3}, MinHash estimate {:.3}", inter as f64 / (s0.len() + s1.len() - inter) as f64, est);
    for s in [0.5f64, 0.8] { println!("P(candidate | s={s}) = {:.3}", 1.0 - (1.0 - s.powi(5)).powi(20)); }
    println!("clusters: {:?}", dedup(&sigs, 20, 5, 0.5));       // docs 0,1,2 share a root
}

Complexity and constants

• Signing: L·k hash evaluations per document (L shingles). A 2 KB web page has order of 300-400 word 5-grams, so k = 128 means about 50k multiply-mods, order of 50-100 µs per document per core.
• One-permutation hashing (one hash, split the range into k bins, take the min per bin) cuts signing to O(L + k).
• Band tables: n entries per band. Distributed: emit (band, band_hash) → doc_id, shuffle by key (MapReduce or Spark), then union-find on the candidate edges.
• Storage: b-bit MinHash keeps only the low 1-2 bits per slot for verification, at the cost of a larger k for the same variance.

Efficiency

• Cost: signing is L·k hash evaluations; a 2 KB page with order of 300-400 word 5-grams at k = 128 is about 50k multiply-mods, order of 50-100 µs per core. A signature is 512 B at 32-bit slots. Compute-bound when signing, shuffle-I/O-bound when band-bucketing a large corpus.
• Levers:
  • One-permutation hashing — signing O(L + k) instead of O(L·k), about k times fewer hashes (Li et al. 2012) — long documents.
  • b-bit slots — 1-2 bits instead of 32, 16-32x smaller signatures (Li and König 2010) — verification storage, at the cost of a larger k.
  • Tune bands b and rows r to the Jaccard threshold — only collisions are verified, not all n² pairs — always.
  • Union-find over band-collision edges — near-linear clustering of candidates — corpus-scale dedup.
  • Exact dedup of normalized text first — drops identical copies before signing (order of) — web crawls.
• Naive — pairwise Jaccard on shingle sets · O(n²·L)
• Standard — k = 128 MinHash signatures + LSH bands + verification · O(n·L·k) to sign, O(n) buckets
• State of the art — one-permutation signing, distributed band shuffle, union-find (FineWeb-style pipelines) · O(n·(L + k)) plus shuffle

Implementation notes

• Store each signature slot as u32 (the low 32 bits of the 61-bit value) to halve memory. A false slot match then has probability 2⁻³², negligible next to the estimator's variance.
• Use (a·x + b) mod (2⁶¹ − 1) with u128 multiply, or two independent 64-bit hashes combined (h1 + i·h2) for speed. Do not use x XOR seed_i with one hash: the minima are correlated.
• Very short documents (fewer shingles than n) produce noisy estimates. Treat them separately or use character shingles.
• Process in two passes over storage: compute signatures (embarrassingly parallel), then band, join and cluster. Keep signatures on disk as u32 or u64 arrays.
• Connected components over-merge chains (A~B, B~C, but A≁C). For corpora that is usually acceptable; otherwise verify against the cluster representative.
• Dedup across all data sources together, and against evaluation sets (decontamination).

Pitfalls

• Banding without verification: false-positive candidates merge unrelated documents into large clusters through union-find.
• Boilerplate-dominated pages (cookie banners, navigation) look like duplicates of each other. Extract the main text first.
• Thresholds tuned on English break on code (much repeated syntax) and on languages without spaces.
• Changing seed, k or shingle size between runs: signatures are not comparable across runs.
• Deduplicating after tokenization and packing: duplicates are already split across sequences.

Variants and alternatives

In production

FineWeb and datatrove (MinHash, 5-grams, 14 × 8), The Pile and RedPajama dedup pipelines, datasketch (Python MinHash LSH), Spark MinHashLSH, text-dedup, Google's near-duplicate web detection (SimHash), BigCode The Stack (MinHash on code files), Mash and sourmash (MinHash sketches of genomes).

Implementations

Sources

• Ondov et al., Mash: fast genome and metagenome distance estimation using MinHash, Genome Biology 2016. paper · code
• Broder, On the Resemblance and Containment of Documents, Compression and Complexity of Sequences 1997. paper
• Broder, Glassman, Manasse, Zweig, Syntactic Clustering of the Web, WWW 1997.
• Leskovec, Rajaraman, Ullman, Mining of Massive Datasets, ch. 3, Cambridge University Press. paper
• Lee et al., Deduplicating Training Data Makes Language Models Better, ACL 2022. paper
• Charikar, Similarity Estimation Techniques from Rounding Algorithms, STOC 2002. paper
• Manku, Jain, Das Sarma, Detecting Near-Duplicates for Web Crawling, WWW 2007. paper
• Li, Owen, Zhang, One Permutation Hashing, NeurIPS 2012.
• Li and König, b-Bit Minwise Hashing, WWW 2010. paper
• Penedo et al., The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale, NeurIPS 2024 Datasets and Benchmarks. paper