DEV Community

Rhea Kapoor
Rhea Kapoor

Posted on

My Battle Against Training Data Duplicates: Implementing MinHash LSH at Scale

The Duplication Problem Nobody Warned Me About

When I first processed 100 million text documents for an open-source LLM project, storage costs ballooned by 40% within weeks. Profiling revealed the ugly truth: 22% near-duplicate content. Traditional SHA-1 hashing missed semantic rewrites like "fast car" vs "quick automobile", while embedding comparisons choked our cluster. That's when I rediscovered MinHash LSH—not as theoretical magic, but as a practical scalpel.

Why Exact Matching Fails for Real-World Data

Most tutorials oversimplify deduplication. After benchmarking three approaches on 10M web pages, the tradeoffs became clear:

Method Precision Recall Throughput Memory/1M docs
Exact Hashing (SHA) 99.9% 17% 280K docs/s 5GB
BERT Embeddings 92% 89% 1.2K docs/s 48GB
MinHash LSH 88% 94% 85K docs/s 11GB

Semantic matching detected paraphrased content but required GPU acceleration to be viable. For our petabyte-scale dataset, only MinHash LSH balanced accuracy with resource constraints.

How MinHash LSH Actually Works (The Bits That Matter)

The textbooks get one thing wrong: real-world implementation isn’t about perfect Jaccard math. It's about avoiding four fatal pitfalls:

Pitfall 1: Shingle Sizing

Using k=5 word shingles on legal documents gave 99% similarity for contracts differing only in dates. Fixed with hybrid shingling:

def hybrid_shingle(text, k_range=(3,6)):  
    return {text[i:i+k] for k in k_range for i in range(len(text)-k+1)}
Enter fullscreen mode Exit fullscreen mode

Pitfall 2: Hash Collisions

I initially used 32-bit hashes for 1B+ documents. Bad idea. Collisions created false positives. Switched to 128-bit MurmurHash3:

uint64_t hashes[4];  
MurmurHash3_x64_128(text, len, seed, hashes);
Enter fullscreen mode Exit fullscreen mode

Pitfall 3: LSH Band Tradeoffs

Through trial-and-error on news article datasets:

  • 20 bands x 6 rows: 98% recall, 15% false positives
  • 15 bands x 8 rows: 93% recall, 8% false positives The sweet spot emerged at 18x7 through iterative calibration.

Integration Headaches You Can't Avoid

When implementing this in a distributed system, three issues cost me sleepless nights:

1. Signature Storage Overhead

Storing 128 uint64 hashes per document consumed 1KB/doc. For 10B docs: 10TB storage. Solved with delta encoding:

Original: [4832, 5921, 8843...]  
Encoded:  [4832, +1089, +2922...]  # 60% size reduction
Enter fullscreen mode Exit fullscreen mode

2. Bucket Skew in Distributed LSH

Nodes handling common shingles (e.g., "click here") became bottlenecks. Mitigated with consistent hashing:

3. Re-Ranking Bottleneck

Verifying candidate pairs consumed 70% of runtime. Optimized with SIMD Jaccard:

__m512i simd_and = _mm512_and_epi64(v1, v2);  
__m512i simd_or = _mm512_or_epi64(v1, v2);
Enter fullscreen mode Exit fullscreen mode

Deployment Lessons From Production

In our Kubernetes cluster processing 2M docs/minute:

  • Cold Starts Killed Us: Pre-warming worker pods reduced tail latency by 8x
  • Indexing Throughput: CPU-optimized instances outperformed GPUs for MinHash by 3.1x/$
  • Error Handling: Forgot to handle LSH band hash collisions initially - added probabilistic fallback

Where I'd Take This Next

The experiment exposed new questions:

  • Can we adaptively adjust LSH bands per data domain?
  • Would weighted MinHash improve results for code deduplication?
  • Could we replace re-ranking with learned models?

Final Thoughts for Practitioners

MinHash LSH isn't a silver bullet. For datasets under 10M documents, exact hashing may suffice. But when scaling to billions like we did:

# Critical parameters in prod  
config = {  
    "shingle_k": 5,               # Optimal for English  
    "hash_bits": 128,             # Collision safety  
    "signature_size": 96,         # Dims  
    "bands": 18,                  # Balance recall/FP  
    "rows_per_band": 7,  
    "jaccard_threshold": 0.85     # Post-filter cutoff  
}
Enter fullscreen mode Exit fullscreen mode

The real value emerged in unexpected places: detecting license violations in code and identifying AI-generated content farms. Sometimes the oldest algorithms deliver the sharpest solutions.

What have your experiences been with large-scale deduplication? I'm particularly curious about multi-language strategies.

Top comments (0)