Scalable
Visualization & Analytics

At sixteen orders, exact tracking is free. A Python set of restaurant names, an exact counter per restaurant, a full histogram of every value that ever appeared — all trivially small. Citywide, at 46,080 orders a day across (Section 3.4's estimate) roughly 1,200 distinct restaurants, "just keep an exact record" stops being a rounding error and starts being a real memory and bandwidth bill, paid every single day, forever.

Every approximate structure in this chapter answers its question using a FIXED amount of memory, chosen in advance, regardless of how large the true dataset grows. That single property — memory that doesn't scale with cardinality — is the entire reason any of them exist.

Worked Example · The Bill for "Just Store Everything"

Practice

1. If CityCourier's distinct-restaurant count grew from 1,200 to 12,000 (10×), what happens to the exact set's memory cost, and what happens to a fixed-size HyperLogLog sketch's memory cost?
   Solution

   The exact set grows 10×, to roughly 96,000 bytes — linear in the count, as always. The HyperLogLog sketch's memory doesn't change at all; the same 256-byte sketch answers the question for 12,000 distinct items too, just with the same ~1% error rate it always had, regardless of the true count.

2. A system needs to know EXACTLY which specific restaurants have ordered, not just how many. Would a HyperLogLog sketch answer that?
   Solution

   No — HyperLogLog only estimates the COUNT of distinct items, and by design never stores or can reconstruct which specific items were seen. A system that needs the actual identities back needs an exact structure (or a different sketch entirely); approximate cardinality and "give me the list" are fundamentally different questions.

3. Why might the exact set actually be the right choice at CityCourier's current, un-scaled size, even though this section argues for approximation?
   Solution

   Because at 1,200 restaurants (or fewer), 9,600 bytes is genuinely nothing — smaller than the sketch's own error-handling code, arguably. Approximate structures earn their keep at the point where exact tracking's LINEAR growth actually starts to hurt; below that point, exactness is free and strictly better.

4. Section 4.3 distinguished a cache (a performance optimization, not a durability guarantee) from a replicated block (a durability guarantee). Is a Bloom filter's "maybe present" answer closer to a cache or to a replicated block, in terms of what you can trust it for?
   Solution

   Closer to a cache — it's explicitly a probabilistic shortcut, not a source of truth. Exactly as a cache miss falls back to recomputing from source, a Bloom filter's "maybe present" typically triggers a fallback to an authoritative check, never stands alone as the final answer to something that actually matters.

A Bloom filter is a bit array of size m, plus k hash functions. Inserting an item sets k bits (one per hash function). Checking an item reads the same k positions: if ANY is still 0, the item was definitely never inserted. If ALL are 1, the item was probably inserted — probably, because some other combination of items could have set those same bits by coincidence.

Worked Example · Five Restaurants, Twenty Bits

Insert CityCourier's five known restaurants into a 20-bit array using 2 simple hash functions:

7 of 20 bits end up set (some restaurants share positions by coincidence — Pizza Barn's two hashes collide with each other, and with Curry Point's and Momo Hut's). Now query three never-inserted names:

"Delhi Cafe" was never inserted either — but it hashes to positions 5 and 0, and both happen to already be set (5 by three different real restaurants, 0 by Sushi Go). The filter reports "maybe present." It's wrong, and it was never claiming otherwise: this is a false positive, the one kind of error a Bloom filter is allowed to make.

Practice

1. Using this section's formula, estimate the false-positive rate if the same 5 restaurants were inserted into a 40-bit array instead of 20, keeping k=2.
   Solution

   (1−e^−2×5/40)² = (1−e^−0.25)² ≈ (0.221)² ≈ 4.9% — roughly a third of the 20-bit array's 15.5%, from doubling the array size alone.

2. Would testing "Curry Point" itself (an actually-inserted restaurant) ever return "definitely absent"?
   Solution

   Never — both of Curry Point's bit positions (7 and 5) were set at insertion time and Bloom filter bits are only ever set, never cleared (barring the counting-filter variant). Every genuinely inserted item is guaranteed a "maybe present" (true positive) result, with 100% certainty in that direction.

3. Hub E builds its own Bloom filter for restaurants IT has personally served, separate from Hub N's and Hub S's. A new order arrives at Hub E for a restaurant that only Hub N has served before. What does Hub E's own filter say, and is that wrong?
   Solution

   Hub E's own filter almost certainly says "definitely absent" (correctly — Hub E genuinely never inserted that restaurant), which isn't wrong at all; it's answering "has HUB E seen this," not "has ANYONE seen this." Getting the broader answer needs the merged (OR'd) filter across all three hubs, exactly this section's note box.

4. Section 7.1 distinguished a Bloom filter's role from a source of truth. Sketch a realistic use: CityCourier wants to avoid an expensive database lookup for "is this a brand-new restaurant we need to onboard." How would a Bloom filter fit in, and what still has to happen afterward?
   Solution

   Check the filter first: "definitely absent" skips the database lookup entirely (genuinely new, proceed to onboarding) with full confidence. "Maybe present" still requires the real database lookup to confirm, since it might be a false positive — the filter's job is only to cheaply skip the EXPENSIVE check in the common case where the answer is a clean "no," never to replace the check when the answer might be "yes."

HyperLogLog hashes every item to a long bit string and looks only at ONE property: how many leading zeros appear before the first 1. A short run is common; a long run is rare — specifically, a run of length r should occur with probability roughly 2^−r, purely by chance. See a long run anywhere in the stream, and it's evidence that MANY distinct items have been hashed, since a rare event needed a lot of tries to show up at all. Split the incoming hashes across m buckets, keep only the LONGEST run seen in each bucket, and combine the m longest-runs into one estimate.

Worked Example · Estimating 1,200 Restaurants at Three Sketch Sizes

The standard error follows a known formula, 1.04÷√m — at m=16 that predicts ~26%, at m=256 it predicts ~6.5% (this particular run happened to land closer to the truth than its own typical spread, which is normal statistical variation, not a broken formula). Quadrupling the buckets roughly halves the expected error, every time — a genuine dial, not a leap of faith.

Try the Dial

Practice

1. Using the 1.04/√m formula, what bucket count would be needed to target roughly a 2% standard error?
   Solution

   1.04/√m = 0.02 → √m = 52 → m ≈ 2,704, rounded up to a convenient power of two (4,096 in most real implementations) — still only a few kilobytes for a 2%-accurate distinct count at any true cardinality.

2. Two independently-run 256-bucket HyperLogLog sketches, one per data center, need to be combined into a single global distinct-restaurant count. What's the actual merge operation?
   Solution

   Take the elementwise maximum of the two sketches' 256 registers, one bucket at a time, producing a single merged 256-register sketch — then apply the same estimation formula to the merged result. No raw data or restaurant names are ever exchanged between data centers, only the 256 register values.

3. A dashboard needs "distinct restaurants today" refreshed every few seconds, at citywide volume. Why would an exact hash-set implementation struggle here in a way a HyperLogLog sketch wouldn't?
   Solution

   An exact set has to be read, updated, and (for a live dashboard) possibly transmitted on every refresh, with a size that grows all day; a HyperLogLog sketch stays at a small, fixed size (256 bytes, say) regardless of how many restaurants have been seen so far, making every refresh cost the same small, predictable amount of work no matter how the day's true count has grown.

4. Section 6.3's K-means recompute step summed local (sum, count) pairs across machines. Is HyperLogLog's max-based merge doing the same kind of aggregation, or a genuinely different one?
   Solution

   Genuinely different — K-means needed an average, which requires a SUM (an associative, additive combination). HyperLogLog's registers need a MAXIMUM, an entirely different (though still associative and commutative) combination rule. Both distribute cleanly by Section 6.1's litmus test, but "sum" and "max" are different operations with different correctness arguments, not the same trick twice.

A Count-Min Sketch is d separate hash tables of width w, each a row of counters. Every occurrence of a key increments one counter in EVERY row (a different hash function per row). To query a key's count, hash it into each row and take the MINIMUM of the d counters found — the minimum, because any single row's counter might be inflated by collisions with other keys, but it's never possible for a counter to hold LESS than the truth.

Worked Example · Seventeen Restaurants, One Hour

A 3-row, 8-wide sketch (d=3, w=8), fed one hour of orders across 17 restaurants including the skewed Curry Point chain:

Every single estimate is at or above the truth — never once below. But look at the SHAPE of the error: Curry Point's absolute error (+18) is large in raw terms but tiny relative to its own size (7.8%). Grill House's absolute error (+21) is actually bigger in raw terms, yet relative to Grill House's true count of 9, that's a 233% distortion. The sketch's error is roughly uniform in ABSOLUTE terms across all keys — which means it's cheapest, relatively, for exactly the heavy hitters you're usually trying to find.

See the Guarantee

Practice

1. Two machines each keep their own Count-Min Sketch (same d, w, and hash functions) over half of citywide traffic. How is a combined sketch produced?
   Solution

   Add the two sketches cell-by-cell — row 1's counters add to row 1's, and so on. Because every counter is just a sum of increments, and sums distribute across machines cleanly (Section 3.1's litmus test again), the combined sketch is exactly as if all the traffic had gone through one machine's sketch from the start.

2. Would increasing w (the width, more counters per row) or d (the depth, more rows) do more to fix Grill House's 233% relative error?
   Solution

   Increasing w — more counters per row means fewer keys collide into the same counter, directly shrinking the overestimation for every key, small or large. Increasing d (more independent rows to take the minimum across) helps guard against a single row having an unusually bad collision, but doesn't shrink the baseline collision rate the way more width does.

3. A key that was NEVER inserted at all is queried against this section's sketch. Can its estimate come back as a large positive number?
   Solution

   Yes — if that key happens to collide, in every one of the d rows, with counters that real keys pushed high (Curry Point's counters, say), the minimum across rows could still be large, purely from collision. This is the Count-Min Sketch analogue of Section 7.2's Bloom filter false positive: a plausible-looking wrong answer, bounded but not impossible.

4. Chapter 3 introduced salting as a fix for a skewed reducer key. Does salting help or hurt a Count-Min Sketch tracking that same skewed key's true frequency?
   Solution

   It would hurt the SKETCH's usefulness for finding the heavy hitter, even though it helps the reduce job it was designed for: salting splits Curry Point's true count across several sub-keys, so any one sub-key's count looks smaller and less obviously "heavy" to the sketch, potentially hiding the very pattern Section 3.4 and this section are both trying to surface. The two techniques solve different problems and can work against each other if applied to the same key without care.

A head-office dashboard rarely asks one flat question. It asks the same data sliced by hub, by time window, by both at once, by neither — and re-running a full aggregation for every slice, on demand, is Section 3's shuffle cost paid over and over for a page that needs to load in under a second.

Worked Example · One Cube, Every Slice For Free

Pre-compute revenue once, cross-tabulated by hub and by Section 1.3's tumbling window — an OLAP cube:

"Revenue by hub" (Chapter 1's original question) is the rightmost column — a roll-up that drops the window dimension by summing across it. "Revenue by window" is the bottom row, the same roll-up in the other direction. The grand total, 5,545, is both dimensions rolled up at once. Every one of these answers was ALREADY computed the moment the 3×3 cube itself was built; none of them need the raw 16 rows touched again.

The Other Half: Rendering

Suppose the dashboard also wants a literal scatter plot of every order's amount versus delivery time, citywide, for the whole day. 46,080 points on one chart is not a chart — it's a solid smear of ink, unreadable at any zoom level a screen can show.

Sampling for rendering is a genuinely different problem from Section 7.1's sketches: those trade memory for a controlled COUNTING error. Downsampling for a scatter plot trades render time and legibility for a controlled REPRESENTATION error — the 3,000 shown points need to be a fair, unbiased sample of the 46,080 real ones, exactly Section 6.5's "any 20% with equal probability" bar, applied to pixels instead of a train/test split.

Practice

1. Add a restaurant dimension (5 values) to this section's hub×window cube. How many cells does the full cube now have?
   Solution

   3 (hub) × 3 (window) × 5 (restaurant) = 45 cells — the pitfall box's multiplicative growth rule, not an additive one.

2. Using the cube in this section, what's Hub N's revenue in window W2 specifically, without recomputing anything from the raw 16 rows?
   Solution

   ₹545 — read directly from the Hub N row, W2 column of the pre-built cube.

3. At 10× today's citywide volume (460,800 orders/day), how many points would need to be sampled to keep the same readable-scatter target of ~3,000?
   Solution

   Still about 3,000 — the render budget is set by what a screen and a human eye can distinguish, not by how much data exists. The DOWNSAMPLE RATIO gets more extreme (460,800÷3,000 ≈ 153.6× instead of 15.4×), but the target point count barely moves.

4. This chapter opened by calling every structure in it a memory-or-speed-for-accuracy trade. Is a pre-computed OLAP cube also making that trade, or something else?
   Solution

   A different trade, and a more familiar one: a cube spends STORAGE (every roll-up, precomputed and kept) to buy QUERY SPEED, with NO accuracy loss at all — every cube answer is exact. Sections 7.2–7.4 traded accuracy for memory; Section 7.5's cube trades memory for speed while keeping accuracy perfect, and its downsampled scatter plot (a genuinely different half of this section) trades fidelity for legibility instead. Three different trades, three different currencies, in one closing section.

1. A Bloom filter says "definitely absent" for a restaurant that was, in fact, inserted earlier. Is this possible?
   Solution

   No — a genuinely inserted item's bits are always set, so it can never return "definitely absent." Only false POSITIVES are possible, never false negatives.

2. A HyperLogLog sketch with 64 buckets estimates 1,086.7 against a true count of 1,200. Does increasing to 256 buckets guarantee an estimate closer to 1,200?
   Solution

   Not a guarantee for any single run — it reduces the EXPECTED error (the standard error shrinks from ~13% to ~6.5%), but any individual estimate is still a random draw around the truth, which can occasionally land further off despite the better expected accuracy.

3. Why does a Count-Min Sketch's minimum-across-rows query rule guarantee no underestimation?
   Solution

   Every row's counter for a key can only be inflated by collisions with other keys (adding extra count), never reduced below the key's true contribution. Taking the minimum across several such counters picks the LEAST-inflated available estimate, which is still ≥ the truth.

4. An OLAP cube has dimensions hub (3), window (3), and restaurant (5). How many cells hold the fully rolled-up grand total?
   Solution

   Exactly 1 — rolling up every dimension collapses the whole 45-cell cube to a single grand-total number, regardless of how many dimensions or cells the full cube has.

5. Which of this chapter's structures would help answer "list every restaurant CityCourier has ever partnered with"?
   Solution

   None of them, directly — Bloom filters, HyperLogLog, and Count-Min Sketch all discard the actual item identities by design. That question needs an exact structure (a set, a database table); this chapter's sketches only answer membership, count, or frequency questions, never "give me the list."

6. Two machines each hold a Count-Min Sketch over half of CityCourier's citywide traffic. What operation combines them correctly?
   Solution

   Cell-wise addition — add each row's corresponding counters together, since every counter is fundamentally a sum of increments and sums distribute cleanly across machines.

7. A dashboard's scatter plot samples 3,000 of 46,080 daily orders. Is this the same kind of operation as Section 6.5's train/test split?
   Solution

   The same FAIRNESS requirement (any point should have had an equal chance of being the one shown, just as any row should have had an equal chance of landing in the test set), applied to a different purpose — legible rendering instead of unbiased model evaluation.

8. Would a Bloom filter, a HyperLogLog sketch, and a Count-Min Sketch all built over the exact same stream of restaurant names take up the same amount of memory?
   Solution

   Not necessarily — each has its own independent size parameter (m bits for the Bloom filter, m buckets for HyperLogLog, d×w counters for Count-Min Sketch), chosen based on that structure's own accuracy target, not tied to the others or to how large the underlying stream happens to be.

• Mining of Massive Datasets — Leskovec, Rajaraman & Ullman. Its stream-mining chapters cover Bloom filters, cardinality estimation, and frequency-moment sketches (Sections 7.2–7.4) as a connected family, with the underlying probability arguments worked in full.
• Designing Data-Intensive Applications — Martin Kleppmann. Frames materialized views and pre-aggregation (Section 7.5's OLAP cube) as instances of a general derived-data pattern that recurs across this entire course.
• Spark: The Definitive Guide — Chambers & Zaharia. Covers Spark SQL's approximate aggregation functions (approx_count_distinct, and similar), which are production implementations of exactly Sections 7.3 and 7.4's ideas.