From the notebook
Finding near-duplicate documents with MinHash and LSH before you index them for RAG
Duplicate and near-duplicate documents waste a RAG index and crowd out diverse results. How shingles, Jaccard similarity, MinHash signatures and LSH banding find near-duplicates in pure Python, and why two versions of a policy with different numbers must not be deduplicated.
Document collections are full of near-duplicates: the same policy exported twice, a page with a new footer, version 1 and version 2 of a contract. Indexed for RAG, they fill the top-k results with copies of one passage and crowd out everything else. MinHash finds them efficiently: split each document into overlapping word shingles, and compare documents by Jaccard similarity (shared shingles ÷ all shingles). MinHash compresses each document into a short signature whose matching positions estimate Jaccard, and LSH banding finds candidate pairs without comparing every document to every other. One warning from my test: two versions of a policy with different numbers are 66% similar. Deduplicate copies; never deduplicate versions.
Shingles and Jaccard similarity
A shingle is a run of k consecutive words. Two documents that share most of their 5-word runs are near-copies; a reworded document shares few.
import re def shingles(text: str, k: int = 5) -> set[str]: words = re.findall(r"\w+", text.lower()) return {" ".join(words[i:i + k]) for i in range(max(1, len(words) - k + 1))} def jaccard(a: set, b: set) -> float: return len(a & b) / len(a | b) if a | b else 1.0
Exact Jaccard needs every pair of documents compared shingle by shingle: fine for a hundred documents, too slow for a million.
MinHash: a signature that estimates Jaccard
Hash every shingle with a seeded hash function and keep the minimum. The chance that two documents have the same minimum equals their Jaccard similarity. Repeat with 128 different seeds, and the fraction of matching positions estimates it:
import hashlib def _h(seed: int, s: str) -> int: return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8, salt=seed.to_bytes(8, "little")).digest(), "little") def minhash(sh: set[str], num_perm: int = 128) -> list[int]: return [min(_h(seed, s) for s in sh) for seed in range(num_perm)] def estimate(sig_a: list[int], sig_b: list[int]) -> float: return sum(x == y for x, y in zip(sig_a, sig_b)) / len(sig_a)
blake2b with a salt gives deterministic seeded hashes from the standard library. Python’s built-in hash() is randomised per process, so signatures stored in one run wouldn’t match the next.
LSH: finding candidates without comparing everything
Split each 128-number signature into 32 bands of 4. Two documents that are identical in any band land in the same bucket and become a candidate pair; only candidates are compared.
from collections import defaultdict def near_duplicates(docs: dict[str, str], threshold: float = 0.8, bands: int = 32) -> list[tuple[str, str, float]]: """LSH: split each signature into bands; documents sharing any identical band become candidates.""" sigs = {doc_id: minhash(shingles(text)) for doc_id, text in docs.items()} rows = len(next(iter(sigs.values()))) // bands buckets = defaultdict(set) for doc_id, sig in sigs.items(): for b in range(bands): buckets[(b, tuple(sig[b * rows:(b + 1) * rows]))].add(doc_id) candidates = {tuple(sorted(pair)) for ids in buckets.values() for pair in _pairs(ids)} found = [(a, b, estimate(sigs[a], sigs[b])) for a, b in candidates] return sorted([f for f in found if f[2] >= threshold], key=lambda f: -f[2]) def _pairs(ids): ids = sorted(ids) return [(a, b) for i, a in enumerate(ids) for b in ids[i + 1:]]
More bands with fewer rows catch lower similarities but produce more candidates to check. With 32 bands of 4, the chance a pair becomes a candidate is 1 - (1 - s⁴)³²: almost certain at 0.8 similarity, about 87% at 0.5, and about 5% at 0.2.
What did the test show?
Four documents: a refund policy, the same policy with a “Last updated” line, a version 2 where 14 days became 30 and 5 business days became 7, and an unrelated shipping page.
| Pair | Exact Jaccard | MinHash estimate |
|---|---|---|
| Policy vs its copy | 0.92 | 0.93 |
| Policy v1 vs v2 | 0.66 | 0.62 |
| Policy vs shipping page | 0.00 | 0.00 |
At a 0.8 threshold, only the copy is found, which is right. At 0.5, version 1 and version 2 are flagged as duplicates. Dropping one of them by similarity alone could leave the outdated refund period in the index. That’s the case to design for.
How should you act on duplicates?
- Copies (above ~0.9): keep one, preferably the canonical URL or newest file, and record the others as aliases so citations still resolve.
- Versions (same document, different content): don’t drop either blindly. Keep the current one in the index and archive the rest, using dates or version metadata, not similarity.
- Boilerplate shared across many documents (headers, disclaimers) inflates similarity; strip it before shingling.
Deduplication changes what retrieval returns, so measure before and after with the metrics in how to evaluate a RAG system. How you split documents matters too; see RAG chunking strategies.
Summary
- Near-duplicates waste a RAG index and crowd out diverse results.
- Shingle documents, estimate Jaccard with MinHash, and find candidates with LSH banding.
- Use deterministic hashes, not Python’s randomised
hash(). - Drop copies; resolve versions with metadata, because similar text can carry different facts.
Related: hybrid search with BM25 and RRF and embeddings and vector search, explained.