Quality and deduplication: MinHash, LSH and measured decisions

Two questions, not one filter

Deduplication asks whether content is repeated under a declared equivalence or similarity policy. Quality filtering asks whether it is useful for a target corpus. A unique document can be poor; a repeated document can be excellent; neither judgment establishes rights or privacy. This lesson implements a bounded near-duplicate candidate index with exact verification, demonstrates learned scoring on authored text and gives a complete unexecuted fastText procedure.

Bring the manifest/filter/shard pipeline from DL046 and exposure accounting from DL048. The aim is to understand the probability and failure modes well enough to design a measured production pipeline—not call30 lines of Python “production-grade100M-document dedup.”

1 · Shingles, Jaccard and a corrected example

For token n-grams, turn each document into the set of its overlapping length-n sequences. Jaccard similarity is intersection size divided by union size. Word order matters within shingles; set membership discards multiplicity. It is not semantic similarity and can miss paraphrases or reordered short sentences.

The original example compared “The president visited Tokyo on Tuesday to discuss trade.” with “On Tuesday, the president visited Tokyo to discuss trade issues.” It claimed about.8 Jaccard on5-word shingles. Under the stated lowercased whitespace-split policy, the intersection is empty: J=0, even though the sentences discuss the same event. This is precisely the distinction the example should teach.

import math,hashlib,json,random
from collections import defaultdict,Counter
 
def shingles(text,n=5):
    if n<=0:raise ValueError('positive shingle size required')
    words=text.lower().split()
    return {tuple(words[i:i+n]) for i in range(max(0,len(words)-n+1))}
 
def jaccard(a,b):
    union=a|b
    if not union:raise ValueError('empty-set similarity requires a separate policy')
    return len(a&b)/len(union)
 
a='The president visited Tokyo on Tuesday to discuss trade.'
b='On Tuesday, the president visited Tokyo to discuss trade issues.'
assert jaccard(shingles(a),shingles(b))==0.
assert shingles('too short')==set()
assert shingles('a b c d e') != shingles('e d c b a')
print('corrected Tokyo5-gram Jaccard',jaccard(shingles(a),shingles(b)))

For100M documents there are N(N−1)/2=4,999,999,950,000,000 unordered pairs, about5e15—not exactly1e16. Computing every full set intersection is generally infeasible. MinHash compresses the comparison representation; LSH reduces which pairs are proposed. MinHash alone does not remove quadratic all-pairs enumeration.

2 · Why the minimum estimates set overlap

Imagine a uniformly random permutation of the universe of shingles. The minimum element in A∪B is equally likely to be any union element. The minima of A and B agree exactly when that first element lies in A∩B, hence:

With K independent permutations, the matching-row fraction is a Bernoulli sample mean with expectation J and standard errorsqrt(J*(1-J)/K). At J=.8,K=128, SE≈.03536; this is one standard error, not a guarantee every estimate lies within3.5%. At J=.5,K=128, SE≈.04419. Halving SE requires four times K, not twice.

Practical seeded hashes approximate random permutations; finite collisions and correlations mean the ideal theorem is not an unconditional guarantee for every hash family. Pin normalization, shingle size, hash algorithm, seed sequence, integer width and byte serialization. A seed of0 is not sacred; comparability of the complete contract is what matters.

def signature(shingle_set,k=128,seed=0):
    if k<=0 or seed<0:raise ValueError('positive k and nonnegative seed required')
    if not shingle_set:return None  # short/empty documents take a separate exact path
    values=[json.dumps(s,ensure_ascii=False,separators=(',',':')).encode() for s in shingle_set]
    result=[]
    for i in range(k):
        salt=(seed+i).to_bytes(8,'big')
        result.append(min(int.from_bytes(hashlib.blake2b(v,digest_size=8,key=salt).digest(),'big')
                          for v in values))
    return tuple(result)
 
def estimate(sig_a,sig_b):
    if sig_a is None or sig_b is None or len(sig_a)!=len(sig_b) or not sig_a:
        raise ValueError('comparable nonempty signatures required')
    return sum(x==y for x,y in zip(sig_a,sig_b))/len(sig_a)
 
A={(str(i),) for i in range(100)};B={(str(i),) for i in range(20,120)}
assert math.isclose(jaccard(A,B),2/3)
sa,sb=signature(A),signature(B)
assert signature(A)==sa
print('set Jaccard',jaccard(A,B),'finite-hash estimate',estimate(sa,sb),
      'ideal SE',math.sqrt((2/3)*(1/3)/128))

Replacing x of100 distinct set elements with new elements gives intersection100−x and union100+x, so J=(100−x)/(100+x). Editing x% of words in a string generally disrupts overlapping shingles and does not obey that formula. For an error experiment, construct sets directly, repeat distinct hash families and compare observed spread to ideal SE; do not demand that a single estimate monotonically improves when K grows. In this implementation adjacent seeds reuse almost all salts: seed 0 uses salts 0 through K−1, and seed 1 uses 1 through K. Space trial seeds by at least the largest K. Nonoverlapping salts avoid that exact reuse but do not prove statistical independence of BLAKE2 hashes.

# Set replacements, not word edits: J=(100-x)/(100+x).
reference={(str(i),) for i in range(100)}
error_summary=[]
for replaced in (10,20,40):
    other={(str(i),) for i in range(replaced,100+replaced)}
    truth=(100-replaced)/(100+replaced)
    assert math.isclose(jaccard(reference,other),truth)
    estimates={k:[] for k in (32,128,256)}
    for trial in range(16):
        left=signature(reference,256,seed=trial*256)
        right=signature(other,256,seed=trial*256)
        for k in estimates:estimates[k].append(estimate(left[:k],right[:k]))
    for k,values in estimates.items():
        rmse=math.sqrt(sum((v-truth)**2 for v in values)/len(values))
        error_summary.append((replaced,k,truth,rmse,math.sqrt(truth*(1-truth)/k)))
print('set replacements, rows, J, observed RMSE, ideal SE',error_summary)

3 · LSH bands create candidates, not a threshold guarantee

Split K=b*r signature rows into b bands of r rows. A pair becomes a candidate if at least one band matches. Under the ideal independent-row model:

The common approximationt=(1/b)^(1/r) locates a transition region where candidate probability is roughly1−e^-1, not a hard threshold or exact inflection point. With16 bands of8 rows it is about.7071, not.79; with32×4 about.4204; with8×16 about.8781. The exact50%-probability point is(1-2**(-1/b))**(1/r).

More bands at fixed row count per band give more chances to collide. More rows per band at fixed number of bands require a stronger match. With K fixed these changes trade recall against candidate load. Corpus structure matters: a giant shared-template bucket can still generate quadratic candidates. No O(N log N) worst-case guarantee or universal1000x speedup follows.

class LSH:
    def __init__(self,k=128,bands=16):
        if bands<=0 or k<=0 or k%bands:raise ValueError('bands must divide k')
        self.k,self.b,self.r=k,bands,k//bands
        self.tables=[defaultdict(set) for _ in range(bands)]
    def keys(self,sig):
        if sig is None or len(sig)!=self.k:raise ValueError('signature contract mismatch')
        return [sig[i*self.r:(i+1)*self.r] for i in range(self.b)]
    def add(self,doc_id,sig):
        for table,key in zip(self.tables,self.keys(sig)):table[key].add(doc_id)
    def query(self,sig):
        result=set()
        for table,key in zip(self.tables,self.keys(sig)):result.update(table.get(key,()))
        return result
 
def candidate_probability(s,b,r):
    if not 0<=s<=1 or b<=0 or r<=0:raise ValueError('invalid probability parameters')
    return 1-(1-s**r)**b
 
for b,r in [(16,8),(32,4),(8,16),(64,2)]:
    print('bands,rows',b,r,'transition approximation',b**(-1/r),
          'p50',(1-2**(-1/b))**(1/r),'P(candidate|J=.8)',candidate_probability(.8,b,r))
assert math.isclose(16**(-1/8),math.sqrt(.5))
assert candidate_probability(.5,32,4)>candidate_probability(.5,16,8)

Use full band tuples as in the reference, rather than only a lossy Python hash of a tuple. Python dictionaries handle internal hash collisions by checking equality; storing only a digest loses that check unless the original tuple is retained. Stable serialized band keys are required for cross-process/distributed grouping.

4 · Exact verification and reversible decisions

The coarse sieve should target high recall, but it still has false negatives. Exact Jaccard on candidates can reject pairs below the declared shingle threshold; it cannot recover pairs never proposed or establish semantic equivalence. Calling all candidates duplicates creates avoidable false positives. Estimating J again from the same signature is cheaper but leaves additional decision uncertainty.

The following online policy keeps a document unless it matches an exact normalized hash or a retained representative above the threshold. It logs the retained ID and measured similarity and never deletes the input. Use unique nonempty string IDs, including for rejected records; the implementation rejects ID reuse before changing the index. Sort by a stable priority/ID before processing to make representative choice reproducible. A retry must consult persisted decisions rather than silently reuse an ID for new text. Connected-component clustering is a different policy: AB and BC can merge A/C even if A is not close to C. Decide which semantics you want before grouping train/test data.

class NearDuplicateDecisions:
    def __init__(self,threshold=.8,n=5,k=128,bands=16):
        if not 0<threshold<=1:raise ValueError('threshold must be in (0,1]')
        self.threshold,self.n,self.k=threshold,n,k
        self.index=LSH(k,bands);self.kept={};self.exact={};self.decisions=[];self.seen_ids=set()
    def keep(self,doc_id,text):
        if not isinstance(doc_id,str) or not doc_id or doc_id in self.seen_ids:
            raise ValueError('unique nonempty string document ID required')
        if not isinstance(text,str):raise ValueError('text must be a string')
        self.seen_ids.add(doc_id)
        normalized=' '.join(text.lower().split())
        digest=hashlib.sha256(normalized.encode()).hexdigest()
        if digest in self.exact:
            self.decisions.append(dict(id=doc_id,keep=False,representative=self.exact[digest],
                                       reason='exact_normalized',jaccard=None));return False
        sh=shingles(text,self.n);sig=signature(sh,self.k)
        if sig is not None:
            for candidate in sorted(self.index.query(sig)):
                similarity=jaccard(sh,self.kept[candidate])
                if similarity>=self.threshold:
                    self.decisions.append(dict(id=doc_id,keep=False,representative=candidate,
                        reason='candidate_exact_jaccard',jaccard=similarity));return False
        self.exact[digest]=doc_id;self.kept[doc_id]=sh
        if sig is not None:self.index.add(doc_id,sig)
        self.decisions.append(dict(id=doc_id,keep=True,representative=doc_id,
                                   reason='no_verified_duplicate',jaccard=None));return True
 
engine=NearDuplicateDecisions()
assert engine.keep('a','one two three four five six seven eight nine ten')
assert not engine.keep('b','ONE  two three four five six seven eight nine ten')
assert engine.keep('short-a','red bird') and engine.keep('short-b','blue fish')
assert not engine.keep('short-copy','red bird')
assert engine.keep('different','apple pear grape plum peach orange lemon lime banana cherry')
# Force a collision candidate below threshold; exact verification must keep it.
other='unrelated symbols within this rather different document'
engine.index.add('a',signature(shingles(other)))
assert engine.keep('forced-false-candidate',other)
long_text=' '.join('word'+str(i) for i in range(50))
assert engine.keep('long-original',long_text)
assert not engine.keep('long-near',long_text.rsplit(' ',1)[0]+' changed')
assert engine.decisions[-1]['reason']=='candidate_exact_jaccard'
print('reversible representative decisions',engine.decisions)

For DL046 integration, pass engine.keep as the explicit near-duplicate hook on an already permitted local corpus. Its in-memory state and greedy representative policy are bounded teaching choices. At scale, compute signatures into typed arrays, externally partition/sort band keys, cap or separately handle huge buckets, verify candidate sets and persist decision lineage. Do not claim that signatures and Python hash tables fit64GB merely because raw integers do.

With128 four-byte signature entries,100M documents require51.2GB payload, before IDs, hash-table overhead, sets, strings, buckets and workspace. This reference uses eight-byte hashes, doubling that raw signature payload to102.4GB at100M. Python integers/tuples are larger still. Measure a pilot's resident memory; shard/external-sort rather than extrapolate from packed bytes alone.

5 · Error curves, order sensitivity and contamination tests

Short documents with no n-grams must not all get an all-zero signature and collide. Route them to exact matching, a separately defined shorter-shingle policy or a retained/quarantined category. Case/punctuation normalization changes semantics: lowercasing code can merge distinct identifiers, and removing punctuation can merge different formulas. There is no universal2%-recall benefit or mandatory5-word size for every domain.

A bag-of-words set is Jaccard over unigrams, not a broken hash implementation. It can match documents with the same vocabulary and different order. That does not explain a claimed zero-near-duplicate result by itself; inspect normalization, seeds, band keys, thresholds and candidate counts separately.

from pathlib import Path
 
def scurve_svg():
    svg=['<svg xmlns="http://www.w3.org/2000/svg" width="700" height="360" viewBox="0 0 700 360">',
         '<rect width="700" height="360" fill="white"/>',
         '<text x="30" y="22">Ideal LSH candidate probability, not measured recall</text>',
         '<path d="M60 40V300H680" stroke="black" fill="none"/>']
    for i,(b,r) in enumerate([(16,8),(32,4),(8,16),(64,2)]):
        color=['#1f5ba0','#ae3c24','#2a813c','#8a388e'][i]
        points=' '.join(f'{60+620*j/100:.2f},{300-250*candidate_probability(j/100,b,r):.2f}' for j in range(101))
        svg.append(f'<polyline points="{points}" fill="none" stroke="{color}" stroke-width="2"/>')
        svg.append(f'<text x="{65+i*155}" y="345" fill="{color}">{b} bands x {r} rows</text>')
    svg+=['<text x="300" y="320">Jaccard 0 to 1</text>','<text x="8" y="45">P=1</text>','</svg>']
    return '\n'.join(svg)
Path('batch7-dl-pretraining-scurves.svg').write_text(scurve_svg())
 
# Exact n-gram overlap screening is a bounded contamination signal, not full decontamination.
def contamination_matches(documents,benchmark_texts,n=3):
    protected=set().union(*(shingles(x,n) for x in benchmark_texts))
    return {doc_id:sorted(shingles(text,n)&protected) for doc_id,text in documents
            if shingles(text,n)&protected}
probe=contamination_matches([('leak','prefix solve this exact problem suffix'),
                             ('clean','a genuinely separate example')],['solve this exact problem'])
assert set(probe)=={'leak'}
print('contamination fixture',probe)

For real benchmarks, include prompt/answer/solution variants under a documented policy, use appropriate normalization and inspect common-phrase collisions. Short questions, translations and paraphrases can evade n-gram matching; boilerplate can create false alarms. Keep evaluation quarantined before model/tokenizer/quality-filter fitting. The original claim that GPT-3 saw specific later benchmarks is not established by chronology or a generic C4 audit; cite a specific overlap study before naming a model/dataset pair.

6 · Learned quality: labels define the target

A classifier learns a labeling policy, not an objective universal notion of good text. FineWeb-Edu uses Llama3 annotations and a Snowflake-arctic-embed representation with a trained regression head; its model card says embedding/encoder layers were frozen while the head was trained. DCLM's fastText filter uses a different positive/negative construction and a top-score percentile policy. Neither is the original invented common “10k labels then fastText0–5” recipe.

A numeric class name is not a calibrated regression score. Taking the most likely label and comparing its number to3 discards uncertainty. For ordinal labels, define whether the policy uses expected score, probability above threshold or a trained regression output, then validate calibration, precision/recall and domain-specific retention. A prose-trained educational filter can reject code; audit per-domain false rejection before deployment.

The following complete CPU demonstration trains a small TF-IDF logistic classifier on authored examples. It tests the pipeline contract, not FineWeb/DCLM quality, factuality or generalization. Train/validation groups in a real corpus must be independent; four probes do not establish accuracy.

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import make_pipeline
 
train_text=[
 'a tutorial explains the proof with a worked example',
 'a lesson derives an equation and explains each variable',
 'a guide tests a program and explains a failure case',
 'a chapter compares methods with evidence and limitations',
 'a reference explains definitions and gives examples',
 'an exercise includes a solution and a derivation',
 'buy buy buy cheap discount click now',
 'win free prizes click subscribe discount offer',
 'navigation home contact subscribe cookie banner',
 'sale sale discount best price buy now',
 'click here win prizes free offer now',
 'home menu ads subscribe contact cookie notice']
labels=[1]*6+[0]*6
classifier=make_pipeline(TfidfVectorizer(ngram_range=(1,2)),
                         LogisticRegression(C=10,random_state=49,max_iter=200))
classifier.fit(train_text,labels)
probes=['this tutorial explains a proof and gives an example',
        'buy cheap discount click now',
        'def square(x): return x*x',
        'a difficult legal clause without tutorial phrasing']
probabilities=classifier.predict_proba(probes)[:,1]
assert probabilities[0]>probabilities[1]
assert all(0<=p<=1 for p in probabilities)
print('authored classifier probes, not quality benchmark',list(zip(probes,probabilities.tolist())))

To measure usefulness, vary the threshold on held-out labeled data, report retained-token/domain/language proportions and inspect accepted/rejected samples. Then train matched-budget proxy LMs on retained corpora and evaluate a fixed clean suite. A high classifier F1 against its judge does not guarantee better downstream models, truth, rights or safety.

7 · Complete optional fastText procedure

This callable procedure uses already locally labeled records and an existing fastText installation. It is unexecuted in the current runtime; there is no paid LLM labeling call or dependency/model download. A record contains a group ID, text and binary human/policy label. Train and validation groups must be disjoint before fitting. The code writes the supported label format, trains, saves and reports validation probabilities; threshold selection remains a validation decision, not a fixed five-minute promise.

# Optional reference: official fastText Python API; unexecuted.
def fit_fasttext_local(train_records,validation_records,output_dir):
    from pathlib import Path
    import fasttext,json
    out=Path(output_dir);out.mkdir(parents=True,exist_ok=True)
    if any(out.iterdir()):raise ValueError('empty dedicated output directory required')
    train_groups={r['group'] for r in train_records};val_groups={r['group'] for r in validation_records}
    if train_groups&val_groups:raise ValueError('group leakage')
    def line(record):
        if record['label'] not in (0,1):raise ValueError('binary label required')
        text=' '.join(record['text'].split())
        if '__label__' in text:raise ValueError('reserved training label spelling in text')
        return f"__label__{record['label']} {text}\n"
    train_path=out/'train.txt';train_path.write_text(''.join(map(line,train_records)),encoding='utf8')
    model=fasttext.train_supervised(input=str(train_path),lr=.5,epoch=10,
                                   wordNgrams=2,dim=100,thread=1)
    model.save_model(str(out/'quality.bin'))
    predictions=[]
    for record in validation_records:
        text=' '.join(record['text'].split())
        labels,probs=model.predict(text,k=2)
        mapping=dict(zip(labels,map(float,probs)))
        predictions.append(dict(group=record['group'],truth=record['label'],
                                 p_quality=mapping.get('__label__1',0.)))
    (out/'validation.json').write_text(json.dumps(predictions,indent=2))
    return predictions

For a production experiment, pin the fastText version and training data/model hashes; use a local labeling rubric or already approved generator with traceable prompts and audit samples; stratify validation by source/language/domain; compute confusion matrices and retention at candidate thresholds; save selected threshold with the model; re-score a held-out test once. Truncation to1000 characters is a policy choice that can hide harmful tails. Label/sample budgets and runtime depend on corpus/hardware, not the number of code lines.

8 · Pipeline order, other dedup methods and evaluation

Cheap high-rejection stages often precede expensive stages, but order is a design decision. Classifying all duplicates first may be wasteful; scoring first can help choose the best representative in a duplicate group. If privacy redaction changes text, dedup keys may need recomputing. Benchmark screening and group splitting must prevent leakage into learned preprocessing. Instrument both cost and retained content rather than assert that fastText is always the slowest stage.

Exact document hashing: simple and reproducible, but normalization and hash collisions require a declared policy. Document MinHash/LSH: catches high lexical shingle overlap and permits missed pairs. Exact substring/suffix-array dedup: detects shared spans within otherwise different documents; deleting spans may damage syntax or context, so log offsets and inspect seams. The Lee paper's commonly described50-token substring unit must not be changed to50 characters. Semantic dedup: SemDeDup uses embedding-based clustering/similarity; representation, cluster policy and threshold define what gets removed. A universal cosine.9 rule or adoption claim for every DCLM run is not supported. D4 studies data deduplication/diversification as a separate pipeline.

FineWeb's paper uses112 MinHashes in14 bands of8 over word5-grams and transitive duplicate clustering, with a retained representative per cluster; it is not the original claimed universal128-hash16×8 standard. Its global-versus-per-crawl ablations show that changing dedup scope can change the retained quality distribution. This differs from our exact-verified retained-representative policy. FineWeb/FineWeb-Edu, DCLM and Nemotron-CC are not obtained merely by checking off the same six boxes. Their data snapshots, filters, models, dedup settings and evaluation protocols differ. No generic pipeline guarantees “FineWeb-quality output,” a5–10% false-positive rate or3–5 downstream points. Likewise no13-hour/nine-dollar1TB job is established by the illustrative code.

Lee et al. report reduced memorization and train/test overlap and improved evaluation efficiency/results in studied settings. Dedup does not guarantee zero memorization. A contaminated validation set can look better before dedup and worse afterward because leakage was removed; clean held-out loss and downstream capability are separate metrics. Preserve corpus variants and compare exact-only, fuzzy and span policies at matched processed-token/compute budgets, with repeated seeds and clean evaluation.

9 · Recall and complete answers

1. Why not all pairs at100M? About5e15 unordered pairs. Signatures make one comparison cheap but not the pair count; LSH generates a smaller candidate set in favorable distributions, with possible quadratic worst cases.
2. Why MinHash works? The union's first random-permutation element lies in the intersection with probability J. K independent trials give SEsqrt(J(1-J)/K); practical hash assumptions and finite width qualify the theorem.
3. Expected match fraction at J=.8,K=128? .8, with one-standard-error≈.03536. It is not a deterministic error bound; use repeated trials or confidence intervals.
4. What do32 bands of4 rows imply? Transition approximation≈.42045, wider candidate retrieval than16×8≈.7071. Compute the full probability curve and verify candidates exactly; neither number is a hard dedup threshold.
5. What happens with unigrams? Word order is lost; same-vocabulary different-order documents can appear identical under that metric. It does not mechanically cause zero duplicates. Choose shingle units for the domain and test counterexamples.
6. Must dedup precede classification? Often it saves repeated scoring, but quality-based representative selection can justify another order. Measure costs, privacy transformations and lineage; no fixed30–40% shrink or universally slowest classifier exists.
7. Why use a classifier? It can learn a target label policy beyond simple length/repetition rules. Validate bias, calibration and downstream utility; it cannot certify facts or guarantee a score gain.
8. How screen contamination? Predeclare normalization/unit, index benchmark prompt/answer/solution spans, flag matching records and inspect ambiguous common phrases. Include paraphrase/translation limitations and keep tests out of fitting/tuning. An n-gram filter is evidence of screening, not proof of complete decontamination.
9. Stretch answer: the supplied SVG procedure plots16×8,32×4,8×16 and64×2. All meet at0 and1; there are no interior crossings for these nested band partitions. For 0<s<1 the candidate probabilities are ordered64×2 >32×4 >16×8 >8×16: a matching larger band implies a matching smaller sub-band. Define sharpness as maximum slope. Differentiating gives P'(s)=br*s^(r-1)*(1-s^r)^(b-1) and its interior maximum occurs at s=((r-1)/(br-1))^(1/r). The maximum slopes are about4.330,3.676,7.168 and6.903 respectively. Thus8×16 is sharpest by that metric, nearJ=.875;64×2 is also steep but nearJ=.0887, unsuitable if the desired retrieval transition is around.8. Compare measured recall/candidate load on independently labeled pairs, not steepness alone.
10. Explain the two sieves. MinHash summarizes lexical sets; LSH proposes likely matches; exact verification decides the declared metric threshold. Missed candidates, metric mismatch and representative policy remain separate error sources.

Tomorrow derive the collision probability from independent rows/bands; after a week test short documents, forced false candidates and a paraphrase with no shared5-grams. Keep decisions reversible so a later quality regression can be traced to retained/removed source IDs.

Sources and optional navigation

Mining of Massive Datasets, similarity chapter, Lee et al.2022, FineWeb paper, FineWeb-Edu model card, DCLM, fastText API, SemDeDup, D4, C4 audit. Primary raw snapshots, exact passages and local oracles are retained separately.

Optional inherited resources: MinHash video, FineWeb recipe. Course map · Previous DL048 · Next DL050. Architecture choices follow; data work is not automatically finished merely because the pipeline ran.