Principle:ChenghaoMou Text dedup False Positive Verification MinHash
| Knowledge Sources | |
|---|---|
| Domains | Deduplication, Verification |
| Last Updated | 2026-02-14 21:00 GMT |
Overview
An optional post-clustering verification step that filters false positive duplicate pairs by computing exact Jaccard similarity within candidate clusters from MinHash LSH.
Description
MinHash LSH is a probabilistic method that inevitably produces false positives: document pairs that land in the same LSH bucket but have actual Jaccard similarity below the threshold. False Positive Verification addresses this by: (1) selecting all documents flagged as duplicates, (2) grouping them by their assigned cluster, (3) computing exact Jaccard similarity for all pairs within each cluster using n-gram tokenization, and (4) re-clustering only the verified pairs using a Polars-based assignment.
This step is gated by the check_false_positive configuration flag and trades computation time for precision. For the MinHash pipeline, the verification uses Polars DataFrames with map_elements for pairwise comparison within clusters.
Usage
Use this principle when deduplication precision is more important than speed, particularly on corpora where the LSH threshold is set aggressively (low threshold) and false positives are likely.
Theoretical Basis
The verification step computes exact Jaccard similarity:
Where A and B are the sets of byte n-grams for two documents. A pair is verified as a true positive only if J(A, B) >= threshold.
# Abstract verification logic (NOT real implementation)
for each cluster in candidate_clusters:
for each pair (doc_i, doc_j) in cluster:
ngrams_i = tokenize(doc_i)
ngrams_j = tokenize(doc_j)
if jaccard(ngrams_i, ngrams_j) >= threshold:
mark_as_verified(doc_i, doc_j)