Data Structures for Big Data

Approximate data structures trade a stated error for lower memory or communication. They are useful for cardinality, membership checks, frequency estimates, quantiles, and heavy hitters. They are not interchangeable: a Bloom filter answers likely membership, a HyperLogLog estimates distinct count, and a Count-Min Sketch estimates frequency with collision overcount.

The mechanism at a glance

Figure — Event stream → Hash + version (canonical identity); Hash + version → Local sketch (compatible update); Local sketch → Merge stage (merge matching parameters); Merge stage → Exact sample (estimate validation); Merge stage → Decision API (bounded approximation)

The numbered components identify responsibilities. Follow the labeled arrows rather than treating the numbers as a global execution order. The scenario later in this lesson shows one concrete sequence.

Step-by-step reasoning

1. 1 · Frame

Start with the decision the estimate drives, the error tolerance, update/query ratio, and whether false positives or false negatives are acceptable. A Bloom filter can say “possibly present” or “definitely absent”; it cannot count. For an estimate used to charge money or enforce a hard cap, approximation may be unacceptable.

2. 2 · Model

Bloom filters use bit arrays and hashes; false positives rise as occupancy grows. HyperLogLog uses hashed leading-zero patterns and register maxima to estimate unique values. Count-Min Sketch uses several counter rows and returns a minimum across hashed positions. Heavy-hitter summaries retain likely leaders; quantile sketches summarize distribution rank. Parameters determine memory and expected error.

3. 3 · Scale

Merge summaries only when their hash seeds, dimensions, and semantics match. Partitioned sketches can be combined for distributed aggregation; version and namespace them. Use exact small-set storage when the expected set fits. For deletion, ordinary Bloom filters cannot remove a key safely; counting Bloom filters add cost and introduce counter saturation concerns.

4. 4 · Recover

Compare estimates against a sampled exact reference and monitor error over time. Rebuild when dimensions or hash versions change. Treat sketch loss as recoverable only if raw events can replay it. Never turn “probably absent” into an irreversible denial without accounting for false negatives in the full pipeline.

Contracts and state

The following sketch makes the decision boundary concrete. Field names and capacity assumptions are illustrative; adapt them to the stated product contract.

Bloom(m bits, k hashes): mayContain(key) -> maybe / definitely absent
HLL(registers): add(hash(key)); estimate() -> approximate distinct count
CMS(rows, width): add(key, n); estimate(key) -> upper-biased frequency
All sketches: algorithm + parameters + hash_version + window

Worked example

A crawler uses a Bloom filter to avoid fetching a URL it has already seen. If the filter returns “definitely absent,” enqueue it. If “maybe present,” check the exact durable URL table for important work. A false positive may skip a new URL, so the team measures that risk and periodically reconciles sampled crawl results against exact storage.

Failure walkthrough

A Count-Min Sketch is reused after changing its hash seed; merged counters no longer refer to the same buckets and the result is meaningless. Store algorithm and hash metadata with each shard, reject incompatible merges, and rebuild from retained events. A growing false-positive rate in a Bloom filter often signals capacity assumptions were exceeded.

Figure — Events update versioned sketches → Workers emit compatible summaries → Merge estimates across partitions → Sampled exact counts measure error → Consumer applies stated tolerance

Decisions and trade-offs

Check your understanding

Choose a structure for URL deduplication, unique visitor estimation, and approximate top queries. State where exact storage remains necessary.

Primary documentation

Read the first-party engineering account or official technical reference. Company engineering posts describe the scope and date of that publication; the interview reconstruction and scenarios here are original teaching examples.

Continue the connection

Study YouTube Top K and explain which guarantee from this lesson carries into that topic.

Choose the error contract explicitly

A Bloom filter answers membership with definitely absent or possibly present. A positive can be a false positive, so it must not prove a duplicate where dropping new data is unacceptable. Standard insertion-only Bloom filters do not have false negatives for inserted keys under correct operation; deletion requires another design, such as a counting variant, and its own constraints.

A Count-Min Sketch maintains several hashed counter rows and estimates an item count from their minimum. Collisions overestimate counts for the basic nonnegative-update construction. It does not enumerate heavy hitters by itself; retain candidate identities separately. HyperLogLog estimates distinct cardinality using hashed observations and mergeable registers, but cannot list the distinct items. A reservoir sample supports a representative bounded sample, not exact frequency accounting.

For n expected items and desired false-positive probability p, a Bloom filter needs approximately -n ln(p)/(ln 2)^2 bits, with about (m/n) ln 2 hash functions. For one million items at 1%, this is about 9.6 million bits, or 1.2 MB decimal, and roughly seven hashes. Actual implementation overhead and growth strategy still matter.

Figure — A decision worksheet for Data Structures for Big Data: read the mechanism and its guarantee together.

Operational sketch

insert A -> set bit positions {1,4,7}
query B -> positions {1,4,7} all set -> possibly present
query C -> positions {2,4,7}; bit 2 clear -> definitely absent
positive membership hint -> exact lookup if correctness requires it

A tempting mistake

Approximate structures are unsafe when their error direction contradicts the business rule. A false positive in a cache hint may add a lookup; a false positive used to discard a payment can lose legitimate work.

Transfer exercise

Can a Bloom filter alone deduplicate financial events?

Figure — A ten-bit teaching example showing a possible false positive and a definite negative.