Skip to content
MDM
2025

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.

Bar chart of mean runtime on the full dataset by number of buckets, from 10,000 to 10 million. 10,000 buckets and 3 million or more hit the 300-second limit; 300,000 and 1 million buckets are fastest at about 100 seconds.

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

DatasetLSHBrute force
5,000 tweets0.24 s19 s
5 million tweets100 s220+ 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.