Duplicate detection for ML pipelines. A Bloom filter gate for streams, plus the batch work that actually breaks training runs: duplicate rows, train/test leakage, and re-uploaded datasets.
In one measured run over 2,310 news articles it caught 534 duplicates, cut 23% of the model's training work, and held 2.5 KB of state instead of 3.4 MB -- with no loss of accuracy.
python3 -m pip install -e ".[dev]"
python3 -m bloomgate reportNot sure this is for you? Read
docs/00-is-this-for-you.md first. It lists the
symptoms, compares this against a set, a SQL UNIQUE constraint and an exact
dedup library, and tells you which to use instead. Roughly speaking: if your
data arrives in one batch, or a database already holds your history, use
those -- a Bloom filter is for streams where storing history is not an option.
Already have data? Point it at your own file, no code required:
# streaming: what is in it, how big a filter, and what a gate would do
python3 -m bloomgate inspect headlines.jsonl --field headline
python3 -m bloomgate dedupe headlines.jsonl --field headline
# ML datasets: the checks worth running before you train
python3 -m bloomgate prep train.csv --fields text --dry-run # duplicate rows
python3 -m bloomgate leakage train=train.csv test=test.csv --fields text
python3 -m bloomgate fingerprint train.csv --rows --fields text # re-uploaded?A set is the normal way to answer "have I seen this before?". It is exact, and its memory grows forever, because it has to hold every item you ever put in it.
A Bloom filter answers the same question using a fixed array of bits that you size once, up front:
to REMEMBER an article: hash it 7 ways, set those 7 bits
to ASK about an article: hash it 7 ways, are all 7 bits set?
That is the whole algorithm. Bits get shared between articles, so a new article can occasionally look like one you have seen. That is the only way it fails, and the odds are something you choose: 1% by default, less if you need.
python3 -m bloomgate demo # watch it happen, with the bit positions printed
News aggregators get articles faster than they can train on them, and some fraction are junk: bots reposting yesterday's headline, syndicated stories running twice, feed loops repeating themselves.
Training on a duplicate is not dangerous, it is wasteful. The model already learned that text. A second gradient step on identical input teaches nothing and costs full CPU time -- and at firehose volume that waste is the difference between a model that keeps up and one that falls behind.
The obvious fix, a set of everything seen, is exactly what does not scale.
Same job, same results, about 1,100x less memory.
One run of python3 -m bloomgate report: 20 Newsgroups, three topics, 30% of
articles pasted back in as duplicates, one model learning from a live stream.
| run | offered | trained on | dropped | drop rate | memory | accuracy |
|---|---|---|---|---|---|---|
| No filter (baseline) | 2310 | 2310 | 0 | 0.0% | 0 (stateless) | 0.948 |
| Exact set (perfect dedup) | 2310 | 1777 | 533 | 23.1% | 3,414 KB | 0.951 |
| Bloom filter (p=1%) | 2310 | 1776 | 534 | 23.1% | 2.5 KB | 0.951 |
Four things worth reading off that table:
- The Bloom row matches the exact-set row. Same articles dropped, same accuracy. It differs only in memory: 1,368x smaller.
- Accuracy went up, from 0.948 to 0.951. The baseline spends 534 updates re-learning identical text. Those updates were noise, not signal.
- Work dropped by 23%, and wall-clock time with it (25-35% faster; timings move per machine, the current run is in docs/06-measured-results.md).
- One article was wrongly dropped. The filter rejected 6 of 1,182 held-out articles it had never seen -- 0.51%, against the 1% it was sized for. That is the cost of the memory saving, and it is measured, not assumed.
for article in incoming_articles: # one at a time, like a real feed
if gate.offer(article.headline): # constant time, fixed memory
classifier.observe(article.text) # expensive maths, new articles onlyThat is the whole system: a gate in front, an online learner behind.
- The gate (
bloom.py) -- hashes the itemktimes and setskbits. No stored copy of the item, ever. - The model (
pipeline.py) --HashingVectorizer(text to numbers with no vocabulary to learn, which is what makes it work on a stream) andSGDClassifier.partial_fit(learns one row at a time).
bloom.py imports nothing else from this project. The data structure reads in
one sitting, and a bug in the ML cannot corrupt it.
This is a small, well-understood data structure, and it has sharp edges. All of
them are handled in
docs/04-production-patterns.md, and all of them
are implemented in
examples/05_production_patterns.py.
| Caveat | What it means in practice |
|---|---|
It never forgets. No remove exists |
A filter that sees everything eventually rejects everything. You must rotate it on a schedule. |
| It says "seen" about new items | One real article lost per 100 at p=0.01. Fine for training data, unacceptable for an audit log -- there you add a confirmation store. |
| It matches bytes, not meaning | Two articles with 95% of their words in common are not duplicates to it. Near-duplicate detection needs MinHash, SimHash or embeddings. |
| The error rate degrades with volume | p=0.01 is the rate at capacity. Past capacity it is 17% at 2x and 68% at 4x. Size for expected volume with headroom. |
| The gate costs real time | 4.7 µs/article on 1.9 KB documents, 3.0 µs on headlines, measured on an Apple M1. It hashes bytes, so cost tracks input length -- feed it a headline or a URL, not a book. |
- You need to delete. Use a set, or a filter with a time window.
- You need exactness at small volume. A set is simpler and free of error.
- You need near-duplicate matching. This compares bytes.
- Your stream is unbounded and you cannot rotate.
Requires Python 3.10+. Dependencies: scikit-learn, mmh3, bitarray, plus
matplotlib for the charts.
git clone <repo-url> && cd bloomgate
python3 -m pip install -e ".[dev]"
python3 -m bloomgate demo # 60 seconds, no dataset needed
python3 -m bloomgate report # the full experiment (downloads ~14 MB once)The dataset is cached in ~/scikit_learn_data after the first run. On macOS,
if that download fails with a certificate error, see
troubleshooting.
Formats accepted: .jsonl/.ndjson, .csv, .tsv, .txt (one per line).
$ python3 -m bloomgate inspect headlines.jsonl --field headline
/tmp/headlines.jsonl
rows 4,000
distinct values 2,825
duplicates 1,175 (29.4%)
average length 32 characters
most repeated values:
215 x Bond yields slip on jobs data
210 x Striker hat-trick seals playoff spot
...
Sizing suggestion (capacity = distinct x headroom):
error rate headroom capacity bits k size
--------------------------------------------------------------
1.00% 1.0x 2,825 27,077 7 3.306 KB
1.00% 1.5x 4,237 40,611 7 4.958 KB
0.10% 1.0x 2,825 40,616 10 4.958 KBinspect tells you what your data contains and hands you the sizing. dedupe
runs it through a gate, and always makes a second exact pass so it can report
how many of its own drops were false positives -- a number you cannot get
anywhere else:
$ python3 -m bloomgate dedupe headlines.jsonl --field headline
dropped as duplicates 1,176
kept 2,824
gate memory 4,062 bytes (3.97 KB)
filter fullness 45.8%
exact dedup would drop 1,175
false positives 1 (0.09% of all drops)
$ python3 -m bloomgate dedupe headlines.jsonl --field headline --confirm
...false positives 0 (0.00% of all drops)Useful flags: --write out.jsonl to save the unique values, --confirm for
zero false positives, --headroom and --error-rate to tune.
You pick two numbers -- how many items you expect, and how often you can afford to be wrong -- and the size follows from a formula. A million articles at a 1% error rate is 1.17 MB; ten million is 11.4 MB.
python3 -m bloomgate size --error-rate 0.001 prints the table without
running anything.
from bloomgate import BloomGate
gate = BloomGate(capacity=10_000_000, error_rate=0.01) # 11.4 MB, chosen once
for article in stream: # millions of articles, one at a time
if gate.offer(article.headline): # ~3 us; state stays at 11.4 MB forever
train_on(article)
if gate.filter.fill_ratio > 0.8: # getting full: time to rotate
gate = BloomGate(capacity=10_000_000, error_rate=0.01)Swap BloomGate for ExactSetGate to get exact dedup, or NullGate to turn
dedup off. Same interface, same call site. Full reference in
docs/05-api-reference.md.
src/bloomgate/ the library
bloom.py the Bloom filter -- the entire idea, 200 lines, no internal deps
gate.py NullGate / ExactSetGate / BloomGate behind one interface
pipeline.py HashingVectorizer + SGDClassifier, one row at a time
data.py builds the seeded fake news stream
bench.py throughput and memory measurement
figures.py every chart in docs/figures, generated from live runs
cli.py python -m bloomgate ...
examples/ five runnable scripts, in reading order
docs/ the documentation set (start at docs/README.md)
tests/ 154 pytest tests
| # | Page | What it answers |
|---|---|---|
| 0 | Is this for you? | Start here. Symptoms, and what to use instead if this isn't it |
| 9 | ML pipelines | Leakage, duplicate rows, embeddings, fingerprints, export |
| 8 | Recipes | Copy-pasteable code: your own files, URLs, restarts, Kafka, rotation, monitoring |
| 1 | What a Bloom filter actually is | The idea, the maths, and when not to use one |
| 2 | How the project is put together | Every file, the data flow, the two streaming gotchas that bite |
| 3 | Sizing and error rates | How big to make it, and the three ways people get that wrong |
| 4 | Production patterns | Rotation, sharding, normalisation, confirmation |
| 5 | API reference | Every public function and what it returns |
| 6 | Measured results | A full run, regenerated by one command |
| 7 | Troubleshooting | Every likely error, with its cause |
Each one explains itself as it prints.
python3 examples/01_bloom_filter_by_hand.py # the algorithm, no library, 30 lines
python3 examples/02_gate_the_stream.py # one interface, three gates
python3 examples/03_streaming_text_classifier.py # a real classifier on a real stream
python3 examples/04_measure_the_error_rate.py # measuring the rate honestly
python3 examples/05_production_patterns.py # rotation, sharding, confirmation| Command | What it does |
|---|---|
make demo |
60-second tour of the data structure |
make compare |
the three-way comparison on a live stream |
make report |
the above, plus the results chart and docs/06-measured-results.md |
make bench |
throughput and memory, without the model |
make figures |
regenerate the dataset-free charts |
make inspect FILE |
what is in your file, and how to size a filter |
make dedupe FILE |
run your file through a gate, report the result |
make doctor |
check this machine can run the project |
make prep FILE |
dedupe rows from your dataset and export the clean set |
make leakage SPECS |
find rows shared between splits (train=train.csv test=test.csv) |
make test |
the test suite |
make check |
tests + figures + report -- what CI would run |
Or drive the CLI directly: python3 -m bloomgate demo | size | compare | report | bench | figures | inspect | dedupe | doctor. Useful flags:
--duplicate-rate, --error-rate, --headroom, --seed.
Every number above came from a command, not from a benchmark someone ran once.
make check- Counts are deterministic. The stream is seeded, so articles offered (2,310), articles trained on (1,777) and duplicates dropped (534) reproduce exactly on any machine. Timings do not, which is why they are not quoted here.
- The false-positive rate is measured, not inferred. It comes from offering 1,182 held-out test articles to a filter that had never seen them. Probing with articles the filter had seen would report 100%, which is the bug this project shipped and fixed -- see docs/02.
- The implementation matches the theory. A test asserts the measured error rate sits on the closed-form Bloom curve within 4 binomial standard errors. That is the test a broken hash function fails.
- 154 tests, including the ones that catch the mistakes this project actually
made: bit-order corruption in saved filters,
peekandofferdisagreeing, and probes drawn from the wrong pool.
MIT -- see LICENSE.