Source ingestion → Deduplication (exact + near-duplicate)
What it is
Enterprise corpora are full of copies. Exact copies (same bytes) are easy: same SHA-256. Near copies are the hard part: the same policy PDF re-exported with a new date in the footer, a wiki page cloned and lightly edited, a contract template instantiated 400 times with different names. These have different hashes but 95% identical text.
Deduplication has two levels:
- Exact — content hash on raw bytes (or on normalised text). Keep one canonical copy; record the others as aliases so citations can still point to any location.
- Near — locality-sensitive hashing. MinHash estimates Jaccard similarity of shingle sets (good for "mostly the same words"). SimHash produces a fingerprint where Hamming distance ≈ dissimilarity (compact, good for large scale). Both let you find candidates in sub-linear time with LSH bucketing, then confirm with a real similarity computation.
Dedup can be applied at document level (before parsing — saves the most) and at chunk level (after chunking — catches shared boilerplate, repeated sections, quoted replies in email threads).
How to implement
- Exact, document level. Compute SHA-256 of raw bytes (already done in change detection). Maintain
hash → canonical_doc_id. On a hit, don't parse; add an alias row(alias_ext_id, canonical_doc_id, source_url, acl). - Normalise text before near-dup. Lowercase, collapse whitespace, strip headers/footers/boilerplate (headers / footers / boilerplate stripping), drop dates and page numbers. Otherwise every export differs.
- Shingle. Word 5-grams (or character 9-grams for short texts). Set of shingles per document.
- MinHash signature. 128 permutations → 128 ints per document. Store it.
- LSH bucketing. Split the signature into bands (e.g. 16 bands × 8 rows). Documents sharing any band bucket are candidates. Tune bands/rows for the Jaccard threshold you want (~0.8–0.9 for "same document").
- Confirm candidates with exact Jaccard on shingles (or embedding cosine). Above threshold → cluster; pick a canonical (newest version, most authoritative source, best parser output).
- Chunk level. Same idea on chunk text; drop chunks whose normalised text hash already exists for the same tenant; for near-dup chunks keep the one from the canonical doc.
- Record everything. The dedupe decision is metadata:
canonical_doc_id,dup_cluster_id,dup_similarity. Never silently discard; you need to answer "why isn't my file showing up".
Small example
from datasketch import MinHash, MinHashLSH
import re, hashlib
def normalise(text: str) -> str:
t = text.lower()
t = re.sub(r"\d{1,2}/\d{1,2}/\d{2,4}|\bpage \d+ of \d+\b", " ", t) # dates, page footers
return re.sub(r"\s+", " ", t).strip()
def shingles(text: str, k: int = 5):
w = text.split()
return {" ".join(w[i:i+k]) for i in range(max(len(w) - k + 1, 1))}
def minhash(text: str, perms: int = 128) -> MinHash:
m = MinHash(num_perm=perms)
for s in shingles(normalise(text)):
m.update(s.encode())
return m
lsh = MinHashLSH(threshold=0.85, num_perm=128) # bands/rows auto-tuned for 0.85
canonical = {} # exact-hash → doc_id
def dedupe(doc_id: str, raw: bytes, text: str):
h = hashlib.sha256(raw).hexdigest()
if h in canonical:
return {"status": "exact_dup", "canonical": canonical[h]}
m = minhash(text)
near = lsh.query(m)
if near:
return {"status": "near_dup", "canonical": near[0], "sim_est": m.jaccard(minhash_of(near[0]))}
canonical[h] = doc_id
lsh.insert(doc_id, m)
return {"status": "unique"}
Chunk-level exact dedupe in one line: seen.add(hashlib.sha256(normalise(chunk).encode()).digest()).
Pros
- Retrieval diversity. Top-k covers five facts, not five copies of one.
- Cost. Skipping parse + embed for duplicates is often 20–40% of ingest spend in enterprise corpora.
- Cleaner evals. Duplicate chunks inflate recall@k artificially (the "right" chunk is there five times).
- Smaller index → faster ANN, less memory.
- Chunk-level dedupe removes repeated boilerplate that dominates embeddings.
Cons
- Canonical choice is a policy question. Which copy wins? Newest? The one in the system of record? Wrong choice = citations to a stale or unofficial copy.
- Near-dup thresholds are corpus-specific. Contract templates at 0.85 similarity are different contracts; wiki drafts at 0.85 are the same page.
- Cross-tenant dedupe is a leak. Two tenants uploading the same public PDF must each get their own copy (or a shared copy with correct multi-tenant ACL — complex). Default: dedupe within tenant only.
- State and memory. MinHash signatures for 100M docs = 100M × 128 × 4 bytes ≈ 50 GB. LSH index needs a real store (Redis, Cassandra, or a dedicated service).
- Aliases must be maintained: when the canonical doc is deleted, promote an alias.
When to use
- Any corpus assembled from multiple sources or from file shares (copies are guaranteed).
- Email (quoted replies), support tickets (macros), contracts (templates), regulatory filings (annual re-filings).
- Before any eval that reports recall@k — or your numbers are lies.
When NOT to use
- Near-dup on template-heavy corpora where instances matter (400 NDAs with different counterparties). Use exact dedupe only, or restrict near-dup to specific sources, or dedupe at chunk level (the shared clauses) while keeping each document.
- Across tenants — don't, unless you have a designed shared-corpus tier with explicit ACL merging.
- Very small corpora: exact dedupe only; near-dup machinery isn't worth it under ~10k docs.
Production at scale
Order matters. Exact dedupe before parsing (saves the most). Near-dup after parsing (needs text) but before embedding. Chunk-level dedupe after chunking. Each stage records its decision as metadata.
Tenant-scoped dedupe. Key every hash table and LSH index by tenant_id. The canonical document's ACL is the union of the ACLs of all copies only if you also union the alias references at query time — simpler and safer: canonical per (tenant, hash), aliases carry their own ACL, and a retrieved canonical chunk is shown only if the caller can see at least one alias. Most teams skip this and just accept some duplication across ACL boundaries: correct but wasteful.
Canonical selection policy. Encode it: prefer system-of-record source > newest modified_at > best parser quality score (production per-page heuristics). Store the reason. When canonical is deleted, run promotion: pick the next alias by the same policy and re-point chunks (or re-ingest).
LSH at scale. datasketch is fine for a few million; beyond that, use a distributed approach: compute MinHash in the ingest worker, write bands to a KV store (band_i:hash → [doc_ids]), query on insert. Spark/Flink MinHashLSH for batch backfills. Keep num_perm at 128; halve it for memory if you only need ~0.9 thresholds.
Near-dup confirmation is the expensive step. LSH gives candidates with false positives; confirm with exact Jaccard on stored shingle sets or with embedding cosine (if the chunk embeddings already exist). Cap candidates per document (e.g. 20) to bound the cost on pathological clusters (a template with 50k instances).
Chunk-level boilerplate dedupe. Count chunk-hash frequency across the corpus. A chunk appearing in >N documents (legal footer, email signature, cookie banner) is boilerplate: drop it from the index entirely and feed the pattern back to the boilerplate stripper (headers / footers / boilerplate stripping).
Explainability. Users will ask "why isn't my upload searchable". status=exact_dup, canonical=<id> with a link is the answer. Surface it in the ingest UI.
Evaluation hygiene. Dedupe the golden set's corpus snapshot too; report recall with and without dedupe during the rollout so you can see the true change.
Prod checklist
- Exact dedupe by SHA-256 before parse, tenant-scoped
- Alias table with per-alias ACL and URL; promotion on canonical delete
- Text normalisation (boilerplate/dates stripped) before near-dup
- MinHash + LSH in a shared store; candidate cap; confirmation step
- Threshold tuned per source; template-heavy sources exempt or chunk-level only
- Chunk-hash frequency → boilerplate removal
- Dedupe decision stored as metadata, visible in ingest UI
- No cross-tenant dedupe by default
Metrics to watch
| Metric | Why |
|---|---|
| Exact-dup rate, near-dup rate per source | Cost saved; threshold sanity |
| Duplicate chunks in top-10 (eval) | Retrieval diversity |
| LSH candidate count p95 | Pathological clusters |
| Aliases pointing to deleted canonicals | Promotion bug |
Related
- Change detection — supplies the byte hash
- Boilerplate stripping — normalisation input; consumer of chunk-frequency signal
- MMR — query-time diversity for what dedupe missed
- Tenant/ACL capture — dedupe must respect it