Advanced: Data Structures for Big Data

Some questions are easy with a hash set and impossible at scale. “Has this user seen this post?” across billions of (user, post) pairs. “How many unique visitors today?” across a firehose of events. “Which search terms are trending right now?” over a stream you cannot store. The exact answer needs memory proportional to the number of distinct items, and at big-data scale that memory does not exist. Probabilistic data structures solve these by giving up a precisely-bounded amount of accuracy in exchange for enormous savings in space.

In the interview: when you hear “billions of items,” “unique count,” “have we seen this,” or “trending / top-K over a stream,” and an exact structure would need gigabytes, mention the matching probabilistic structure — Bloom filter, HyperLogLog, or Count-Min sketch — and state the accuracy trade-off. It is a strong senior signal.

Bloom filters: approximate membership

A Bloom filter answers one question — is x in the set? — in a tiny, fixed-size bit array, with a crucial asymmetry: it can say ”definitely not present” or ”possibly present.” It never produces a false negative, but it can produce a false positive.

It works with k independent hash functions over a bit array of size m:

• Insert x: hash x with each of the k functions and set those k bits to 1.
• Query x: hash x the same way. If any of its k bits is 0, x was definitely never inserted. If all k bits are 1, x is probably present — though those bits might have been set by other elements (a false positive).

class BloomFilter:
    def __init__(self, size, k):
        self.bits = [0] * size
        self.size = size
        self.k = k
    def _hashes(self, x):
        return [hash(f"{i}:{x}") % self.size for i in range(self.k)]
    def add(self, x):
        for h in self._hashes(x):
            self.bits[h] = 1
    def might_contain(self, x):
        return all(self.bits[h] for h in self._hashes(x))   # False = definitely absent

The false-positive rate is tunable: more bits and an optimal k drive it down. A filter holding 1 billion items at a 1% false-positive rate needs only about 1.2 GB — versus the tens of gigabytes an exact set of the keys would take, and it answers in O(k) with no pointer chasing.

Where it shows up:

• LSM-tree databases (Cassandra, RocksDB, HBase) keep a Bloom filter per SSTable so a read can skip files that definitely do not contain the key — turning many disk seeks into none.
• Deduplication — “have we already processed this event / sent this email?” without storing every id.
• Cache / crawler filtering — “is this URL already queued?” or avoiding a cache lookup for keys that certainly do not exist.

The rule to remember: a Bloom filter is perfect when a false positive is cheap (you do one extra lookup that comes back empty) but a false negative would be a bug (you must never wrongly claim absence).

HyperLogLog: approximate distinct count

Counting unique elements exactly means remembering every element you have seen — O(n) memory. HyperLogLog (HLL) estimates the cardinality of a huge set in a constant ~12 KB, with a typical error around 2%.

The intuition: hash each element and look at the number of leading zeros in the hash. Seeing a hash with many leading zeros is rare, so it hints the set is large (you would only expect, say, 10 leading zeros after roughly 2¹⁰ distinct items). HLL splits the hash space into many registers, keeps the maximum leading-zero count per register, and combines them with a harmonic mean to produce a robust estimate.

pfadd visitors:2026-04-21 user_8831
pfcount visitors:2026-04-21        # ≈ unique visitors, ~2% error, ~12 KB

It is ideal for unique visitors / unique devices / distinct search terms at scale, and HLLs merge: per-shard or per-hour counters combine into a daily total without double-counting, which exact sets cannot do cheaply. Redis exposes it directly (PFADD / PFCOUNT / PFMERGE).

Count-Min sketch: approximate frequency

A Count-Min sketch answers how many times has x appeared? — frequency, not just membership — in fixed memory. It is a small 2-D array of counters with one hash function per row:

• Increment x: hash x into each row and increment that counter.
• Estimate x: hash x into each row and return the minimum of those counters.

Because different items can collide on a counter, estimates can over-count but never under-count; taking the minimum across rows reduces the collision error. It uses memory independent of the number of distinct items, so it fits a firehose of millions of keys in a few megabytes. It is the workhorse behind heavy hitters / trending / top-K over streams (trending hashtags, most-requested URLs, hot keys for a cache), usually paired with a small heap that tracks the current top-K.

The common theme

All three structures make the same bargain: give up exactness you do not actually need, and the problem collapses from gigabytes to kilobytes.

The engineering judgement is recognising when approximate is good enough. Nobody needs the unique-visitor count to be exact to the person; “about 4.2 million, ±2%” is a perfectly good dashboard number, and it costs 12 KB instead of hundreds of megabytes.

Key Takeaways

1. Probabilistic structures trade bounded accuracy for huge space savings — the right tool when exact answers would need more memory than you have.

2. Bloom filter = approximate membership. No false negatives, tunable false positives. Use it where a false positive is cheap but a false negative is a bug — skipping disk reads in LSM stores, dedupe, cache/queue filtering.

3. HyperLogLog = approximate distinct count. Billions of uniques in ~12 KB at ~2% error, and HLLs merge — perfect for unique visitors across shards and time windows.

4. Count-Min sketch = approximate frequency. Fixed memory, over-counts slightly; the basis for trending / heavy-hitters / top-K over a stream, usually with a small top-K heap.

5. Recognise the signal in the interview: “billions,” “unique,” “have we seen,” “trending over a stream” — reach for the matching structure and state the trade-off. Redis implements Bloom and HLL out of the box.