Near-duplicate detection in 5 million tweets
Finding every pair of near-identical tweets among 5 million, within 5 minutes and about 2 GB of memory, using MinHash and locality-sensitive hashing.
- Kind
- Data engineering
- Context
- Big Data Analytics course, KU Leuven
- Result
- Full dataset in 100 seconds instead of an estimated 220+ days by brute force, with 0.91 recall.
- Built with
- Java, MinHash, LSH, Python, Bash
- Status
- Code private (course rules)
The task
Find all pairs of tweets with a Jaccard similarity above 0.9, measured on 3-character shingles, among 5 million tweets. The limits: 5 minutes and about 2 GB of memory. Comparing every pair would mean around 12.5 trillion comparisons.
How it works
- MinHash signatures. Each tweet gets a short signature built while streaming through the data, so the full dataset is never in memory.
- Banded LSH. Signatures are split into bands and hashed into buckets, one band at a time. Only tweets that share a bucket become candidate pairs.
- Cheap verification. Candidates are checked by comparing signatures instead of the full shingle sets.
Tuning
A systematic grid search over the number of hashes, bands and buckets, measuring balanced accuracy, runtime and peak memory. The final configuration: 50 hashes, 5 bands and 300,000 buckets.

Mean runtime over 10 runs on the full dataset, by number of buckets (50 hashes, 5 bands). A bar at 300 s hit the time or memory limit: too few buckets crowd them with candidate pairs, too many cost too much memory. Figure from the original project.
Result
| Dataset | LSH | Brute force |
|---|---|---|
| 5,000 tweets | 0.24 s | 19 s |
| 5 million tweets | 100 s | 220+ days (estimated) |
Against the exact brute-force answer on a 5,000-tweet subset: balanced accuracy 0.95 and recall 0.91. Peak memory on the full dataset was about 2.2 GB. The brute-force estimate scales the measured 19 s quadratically to 5 million tweets.