DEV Community

Ali Ahmed
Ali Ahmed

Posted on Originally published at aliahmed.si

Finding near-duplicate documents with MinHash and LSH before you index them for RAG

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.

```python title="minhash.py: shingles"
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:



```python title="minhash.py: signatures"
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)
Enter fullscreen mode Exit fullscreen mode

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.

```python title="minhash.py: LSH"
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](https://aliahmed.si/blog/rag-retrieval-evaluation-metrics/). How you split documents matters too; see [RAG chunking strategies](https://aliahmed.si/blog/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](https://aliahmed.si/blog/hybrid-search-bm25-reciprocal-rank-fusion/) and [embeddings and vector search, explained](https://aliahmed.si/blog/embeddings-vector-search-explained/).

---

Written by Ali Ahmed · [Original article](https://aliahmed.si/blog/minhash-near-duplicate-documents-rag/)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)