Large-Scale Bucket-Feasible LSH-MinHash Deduplication

LSH-MinHash deduplication in DataTrove keeps one document per connected component of band collisions. Connectivity does not make every pair a near-duplicate: the largest ClueWeb22 component contains 28.8 million documents, of which one is kept. We instead retain at most one document per collision bucket, reusing DataTrove's four stages—signature generation, band matching, clustering, and filtering. Band-sharded Stage 2.5 pruning removes redundant incidences before single-node, memory-bound clustering. A multi-seed extension reruns the same stages under independent signatures with retuned banding, suppressing low-similarity collisions at a chosen high-similarity recall target; processing survivors sequentially satisfies every round's constraints without materializing a joint bucket family. Within a prior strong independent set framework, intrinsic bucket weights connect exact reductions, selection, and optimality certificates, and an observed-history certificate bounds final retention with a sharp information limit. On 1.62B ClueWeb22 and 3.98B HPLT documents, on the same buckets as legacy unionization, bucket-feasible selection retains 32M/34M more documents; four retuned seeds raise the gain to 64M/65M and lower Stage 3 MaxRSS by $48.36\%$/$5.70\%$. Greedy retention reaches at least $99.43\%$ of the puncturing upper bound in all 20 active seed rounds. Within the 28.8M-document component, the strongest local run retains 1,474,462 documents; exhaustive MinHash comparison of all survivor pairs finds 20 with estimated similarity $\ge 0.75$.