What you will learn
- Explain why near-duplicates hurt both training and evaluation
- Use shingling + MinHash to estimate Jaccard similarity cheaply
- Run MinHash LSH to find near-duplicates without O(n²) comparisons
- Apply a first-seen keep policy so your best sources survive dedup
Why this matters
Duplicate and near-duplicate records quietly wreck AI datasets: they inflate eval scores (the model "memorized" a test item it also saw in training), and they bias training toward whatever topic happens to be over-represented. MinHash deduplication is the standard, scalable way to clean a corpus — and explaining it is a frequent data-engineering interview question.
Why exact-match dedup isn't enough
set(records) only catches byte-identical duplicates. But "What is a refund?" and "what's the refund policy?" are near-duplicates — different strings, same meaning. You need a similarity measure, not equality.
Shingling → MinHash → Jaccard
- Shingle each text into overlapping character k-grams (e.g. 3-grams). Two similar texts share most shingles.
- MinHash turns each shingle set into a small fixed-size signature. Comparing signatures approximates the Jaccard similarity of the original sets — but far cheaper.
- Threshold — if estimated Jaccard ≥
threshold(say 0.8), treat as a duplicate.
LSH avoids the O(n²) trap
Comparing every pair is quadratic and dies on large corpora. MinHash LSH buckets similar signatures so you only compare likely matches. You query the LSH for each record; if something similar already exists, drop it.
First-seen wins — so order matters
The kept record is the first one seen. Order your input so high-quality sources (curated data) come before noisier ones (scraped data). Then dedup keeps the good copy and drops the noisy near-duplicate.
From AI Engineering (Chip Huyen)
Duplicates look harmless, but chapter 8 explains why they cause trouble. Repeated examples skew what the model sees as normal, waste training compute, and can make it memorise and repeat those items. Worse, if copies of test examples sit in the training set, your evaluation measures recall of seen data instead of real ability.
Huyen separates the levels at which duplication happens. Whole documents may repeat, parts of documents may repeat across sources, and examples may be near copies that differ only in whitespace, punctuation or a few words. Exact matching, for example by hashing normalised text, catches the first kind cheaply. Near duplicates need fuzzier methods, such as comparing sets of word sequences with techniques like MinHash, or comparing embeddings and treating very close vectors as copies.
In practice, run exact deduplication first, then a near-duplicate pass with a threshold you have checked by reading the pairs it flags. Always deduplicate across your train, validation and test splits, not only inside each one.
Further reading: Chip Huyen, AI Engineering (O'Reilly, 2025), chapter 8
import re, string
_PUNCT = re.compile("[" + re.escape(string.punctuation) + "]")
_WS = re.compile(r"\s+")
def shingles(text: str, k: int = 3) -> set[str]:
norm = _WS.sub(" ", _PUNCT.sub("", text.lower())).strip()
return {norm[i:i + k] for i in range(len(norm) - k + 1)} if len(norm) >= k else {norm}
def dedupe_records(records: list[dict], threshold: float = 0.8, num_perm: int = 128):
from datasketch import MinHash, MinHashLSH
lsh = MinHashLSH(threshold=threshold, num_perm=num_perm)
kept, n_dupes = [], 0
for i, rec in enumerate(records):
m = MinHash(num_perm=num_perm)
for sh in shingles(rec.get("instruction", "")):
m.update(sh.encode("utf-8"))
if lsh.query(m): # something similar already kept
n_dupes += 1
continue
lsh.insert(f"rec-{i}", m) # first-seen wins
kept.append(rec)
return kept, n_dupesTry it yourself
- Build a list with 5 obvious near-duplicate questions and 5 distinct ones
- Run
dedupe_recordsand confirm it removes ~5 and keeps ~5 - Lower the threshold to 0.5 and watch over-aggressive merging
- Reorder the input so a curated record comes first, and verify it's the survivor
- Time it on 10K records vs a naive O(n²) loop to feel the LSH win
Common mistakes
- Skipping normalization — case, punctuation, and whitespace differences defeat shingling
- Threshold too low — you merge genuinely different items and lose data
- Ignoring order — random order means dedup might keep your noisy copy and drop the clean one
- Using exact-match dedup only — misses the near-duplicates that actually cause leakage
- Deduping after the train/test split — dedup the whole corpus first, or test items leak into train
Checklist
- Implemented shingling with normalization
- Ran MinHash LSH dedup and reported duplicates removed
- Verified first-seen keep policy with deliberate ordering
- Can explain why near-duplicates cause eval leakage
Quick quiz
Q: Why use MinHash LSH instead of comparing every pair of records directly?
How to explain it in an interview
"Exact dedup only catches identical strings, but near-duplicates — same question, different wording — cause real harm: eval leakage and topic bias. I shingle each text into character k-grams, compute a MinHash signature that approximates Jaccard similarity cheaply, and use MinHash LSH so I'm not doing an O(n²) comparison. I keep the first-seen record, and I order the input so curated sources come before noisy ones — that way dedup keeps the good copy. And I always dedup the full corpus before splitting train and test, or test items leak into training."