Topic 0.1
Why Probabilistic Data Structures?
In one line
Exact structures like hash sets store every item, which becomes expensive at billions of items. Probabilistic structures store a compact summary and answer with a controlled error rate, cutting memory by 10–100× when an occasional wrong "maybe" is acceptable.
Think of it like this
A nightclub bouncer with a guest list. An exact list of every name takes a thick binder. A compact alternative is a card with a few tick marks per name pattern: it lets the bouncer instantly turn away people who are definitely not invited, and only people who "might" be invited get checked against the binder at the back.
Key ideas
- 01
Exact membership: a
HashSet<String>of 1 billion 20-character IDs in Java costs tens of gigabytes (object headers, strings, hash table entries). Even compact byte arrays need 20+ GB just for the keys. - 02
Probabilistic membership: a Bloom filter for 1 billion items at a 1% false-positive rate needs about 1.2 GB, regardless of how long each item is, because it never stores the items.
- 03
Two kinds of error: a false positive says "maybe present" for something that isn't; a false negative says "absent" for something that is. A standard Bloom filter has false positives but never false negatives (when used correctly).
- 04
The trade: you choose the error rate. Lower error means more memory (about 4.8 extra bits per item for every 10× improvement). There's no free accuracy.
- 05
The pattern that makes it safe: the filter is a fast pre-check in front of an authoritative store. "Definitely absent" skips the expensive lookup; "maybe" falls through to the real check. A false positive then costs one unnecessary lookup, never a wrong answer.
Code & diagrams
1 billion IDs (~20 bytes each) Memory Answer quality
Java HashSet<String> ~60-100 GB exact
Sorted byte arrays / compact hash table ~24-30 GB exact
Bloom filter, 1% false positives ~1.2 GB "no" exact, "maybe" 1% wrong
Bloom filter, 0.1% false positives ~1.8 GB "no" exact, "maybe" 0.1% wrongInterview problem
The problem
When is approximate good enough?
For each case, decide whether a probabilistic membership structure is acceptable: (1) blocking repeat product recommendations a user has seen, (2) checking if a username is taken before registration, (3) deciding whether a bank account exists before transferring money, (4) skipping disk reads for keys not in a file.
Explain it without notes
Define false positive and false negative, and say which one a Bloom filter can produce.
Practice
Estimate the memory of storing 100 million UUIDs as strings in a HashSet in your language, and compare with a 1% Bloom filter.
Trade-offs
- ↔
Probabilistic structures save huge amounts of memory but give up exact answers; they belong in front of, not instead of, authoritative data.
Done when you can
I can explain why probabilistic structures exist and when an approximate answer is safe.