Finding near-duplicate documents by comparing every pair is O(n²). With 517,401 emails, that’s about 134 billion comparisons. This project builds the standard way around that from scratch in Rust, parallelised with Rayon, and tests it on the Enron email dataset.
Pipeline
- Shingling. Each email is split into overlapping k-word shingles, and each shingle is hashed with xxHash. Variable-length text becomes a set of integers.
- MinHash. m random hash functions shrink each set to a fixed signature of m values. The fraction of matching values between two signatures estimates their Jaccard similarity.
- LSH banding. Each signature is cut into b bands of r rows, and each band is hashed into a bucket. Two documents only become a candidate pair if they collide in at least one band.
- Clustering. Union-Find merges every document that collides in any band into one group of near-duplicates.
Tuning
I swept hashes (m), bands (b) and shingle size (k), then measured precision and recall on a sample against exact Jaccard ground truth. The final choice was m = 200, b = 10, r = 20, k = 5. That puts the S-curve’s tipping point at (1/b)^(1/r) ≈ 0.891, which sits right on the 0.90 similarity threshold.
| Metric | Value |
|---|---|
| Precision | 88.33% |
| Recall | 99.26% |
| F1 | 0.935 |
| Avg similarity of LSH pairs | 0.985 |
The measured results follow the theoretical S-curve. On the full dataset, the pipeline groups 424,025 emails into 125,570 clusters in 7.47 seconds end to end.
The same repo also implements the PCY algorithm for frequent-itemset mining and association rules on grocery basket data.