Data Structures for Big Data

At massive scale, some questions are too expensive to answer exactly. "Have we seen this URL before?" across billions of URLs, "how many unique visitors today?" across hundreds of millions, "how often has this item been requested?" in a firehose of events — storing every element to answer precisely costs gigabytes of memory. Probabilistic data structures answer these approximately, using a tiny fraction of the space. The deal is always the same: accept a small, bounded error in exchange for a huge saving in memory.

Bloom filter — "have I seen this?"

A Bloom filter tests set membership in a few bits per element. It can tell you an item is definitely not in the set, or probably in it — it has false positives but never false negatives.

• Hash each item with several hash functions; set those bits in a bit array.
• To check an item, hash it the same way; if any of those bits is 0, it's definitely absent. If all are 1, it's probably present (could be coincidence).

The win is using it as a cheap first gate before an expensive check:

• "Is this URL already crawled?" — a Bloom filter in memory skips the database for the (vast majority) of never-seen URLs; only a "probably yes" pays for a real lookup.
• Cache / database guard — "is this key possibly in the store?" avoids pointless disk reads for keys that definitely don't exist.

Because a false positive just means "do the real check anyway," the error is safe — you never miss a real member.

HyperLogLog — "how many unique?"

Counting distinct items exactly means remembering every item you've seen. HyperLogLog estimates the cardinality (count of unique elements) of a huge stream in a few kilobytes, with a couple of percent error — by cleverly observing patterns in the hashes of elements rather than storing them.

• "Unique visitors to this page today," "distinct search terms," "unique IPs" — at billions of events, a 1–2% error is invisible and the memory saving is thousands-fold. Redis has it built in (PFADD/PFCOUNT).

Count-Min Sketch — "how frequent?"

Count-Min Sketch estimates how many times each item has appeared in a stream, using a small fixed grid of counters. It can overcount slightly but never undercounts.

• "Top trending items," heavy-hitters, per-item rate limiting at scale — track frequencies for millions of keys in fixed memory instead of a counter per key.

The pattern to recognise

The common thread: each one is small and fixed in size regardless of how much data flows through it, and each has an error that's safe for its use case (a false positive that triggers a harmless extra check; a slightly fuzzy count where exactness doesn't matter).

What to watch

• Only where approximation is acceptable. Never use these for money, inventory, or anything that must be exact.
• Tune the error. More bits/counters → less error → more memory; size them for the accuracy you need.

What to say in an interview

Reach for them when an exact answer is too expensive and a little error is fine:

"Checking whether a URL has been crawled against billions of entries would thrash the database, so I'd put a Bloom filter in front — it tells me 'definitely new' instantly and only a 'maybe seen' pays for a real lookup, with no false negatives. For 'unique visitors' I'd use HyperLogLog to estimate cardinality in kilobytes rather than storing every visitor id, since a 1% error is fine for that metric."

---

Next up: Vector Databases — search by meaning, not keywords.