Streaming Algorithms & Sketches
You cannot store the stream, so you store a sketch — a small, cleverly maintained summary that answers a specific query approximately. This lesson covers the four canonical sketches taught in Stanford's CS246 (Mining Massive Datasets) and MIT's streaming-algorithms courses: a uniform sample, a membership filter, a distinct-count estimator, and a sliding-window counter. Each trades exactness for a dramatic space saving with a provable error bound.
Reservoir sampling: a uniform sample in one pass
Problem. Keep a uniform random sample of elements from a stream whose length you do not know.
Algorithm R (Vitter):
- Put the first elements directly into the reservoir.
- For the -th element (), with probability replace a uniformly chosen reservoir slot with it; otherwise discard it.
Reservoir sampling: a uniform sample in one pass
Each stream element t is taken into the k-slot reservoir with probability k/t (certain for the first k). This exactly maintains a uniform random sample of everything seen so far — without ever knowing the stream's length. Watch the acceptance probability k/t decay: early elements are grabbed eagerly, late ones rarely, and the two effects cancel so every element ends with probability k/t of surviving.
Why it works. We prove by induction that after elements, every element seen so far is in the reservoir with probability exactly .
- Base case: the first elements each start with probability .
- Inductive step: element enters with probability by construction. An element already in the reservoir (probability ) survives if either the new element is rejected, or it is accepted but evicts a different slot:
Every element, old or new, ends at — a uniform sample, in space and work per element.
The proof is short enough to believe and subtle enough to get wrong in code. Step through one run, then watch 200,000 of them audit it:
Reservoir sampling — auditing the uniformity proof
The reservoir holds k = 3 elements and the stream length n is **unknown** — that is the whole constraint, and it is why you cannot just sample k of n at the end. The first 3 elements go straight in, each with probability 1 of being present so far. Everything interesting starts at element 4.
One run of Algorithm R on a 12-element stream with k = 3, showing the acceptance probability k/t falling as the stream grows and which slot each accepted element evicts. Then the part a proof cannot show and a single animation cannot either: 200,000 independent runs measuring how often each element survives. The correct version is flat at k/n within 2.5 standard errors. Two plausible wrong versions — evict the oldest slot, or accept with probability 1/t — keep the acceptance rule the lesson states and still produce sharply biased samples, in opposite directions.
What to notice:
- Frame 6: the proof, measured. Across 200,000 runs every element's survival rate lands within 2.5 standard errors of . Element 1 had to survive nine chances to be evicted and element 12 only had to be accepted once, and they come out equally likely.
- Frame 7: two wrong versions that keep the acceptance rule. Evict the oldest slot rather than a uniformly chosen one and element 1 survives 55× less often than it should. Accept with probability instead of and the reservoir goes stale, holding its first three elements 65% of the time. Both biases are invisible in any single run — the reservoir is always the right size and always holds plausible elements. Only the frequencies reveal them, which is exactly why the induction above is the real deliverable.
Bloom filters: approximate set membership
Problem. Test whether an element has been seen, using far less space than storing the set. Tolerate false positives but never false negatives.
A Bloom filter is an -bit array and independent hash functions. To insert , set the bits to 1. To query , report "present" only if all of those bits are 1. A "not present" answer is always correct; a "present" answer may be a false positive if other insertions happened to set all bits.
After inserting elements, the probability a given bit is still 0 is , so the false-positive rate is
For fixed and , this is minimised at
Reading the formula
More bits per element () shrinks the error exponentially; the optimal number of hashes is . A rule of thumb: ~10 bits per element with ~7 hashes gives a false-positive rate under 1%. That is a few bits to remember whether you have ever seen an item — versus storing the item itself.
Step through a filter small enough to see every bit — 16 bits, 3 hashes, three inserted words, and then watch the false-positive formula get measured:
Bloom filter — set bits, check bits, and the k that minimizes lying
A 16-bit array, all zero, and k = 3 independent hash functions. A Bloom filter never stores the elements themselves — only bits — which is why it can answer membership in a few bits per item instead of however many bytes the item takes.
The contract is deliberately lopsided: a Bloom filter may say "present" about something never inserted, but it can never say "absent" about something that was. That asymmetry is what makes it useful as a cheap pre-filter.
A 16-bit filter with 3 hashes, small enough that every bit is visible. Three inserts, then three queries: a true member (always correct), a true non-member (a single zero bit is proof of absence), and a false positive whose three bits were each set by a different member — nobody's fault individually. The final step measures the false-positive rate against (1 − e^(−kn/m))^k across 12 values of k, and finds a bottom so flat that the exact choice of k barely matters.
What to notice as you step:
- Inserting only ever sets bits. Nothing is ever cleared, which is why a member's bits can never revert and false negatives are impossible — and, in the same breath, why deletion is impossible too. Watch bit 12 get set by "cat" and then re-set by "dog": the filter cannot tell, so it could never safely unset it.
- One zero bit is a proof. The "bird" query stops at the first unset bit, and that answer is exact, not probabilistic.
- The false positive has no single culprit. "dove" hits bits 11, 12 and 13, set by "fish", "cat"/"dog", and "fish" respectively. Three unrelated insertions covered a fourth element's fingerprint between them.
- The last step measures across twelve values of at ~10 bits per element, and finds a bottom so flat that every from 5 to 12 lands under 1%. The rule of thumb above is a robust recipe, not a knife-edge.
Bloom filters are everywhere in streaming ML pipelines: de-duplicating events, skipping cache/database lookups for keys that are definitely absent, and gating expensive feature computation.
Flajolet-Martin: counting distinct elements
Problem. How many distinct items has the stream contained? Storing every distinct value costs ; Flajolet-Martin (FM) does it in bits.
Idea. Hash each element to a uniformly random bit string. Let be the number of trailing zeros in . A random hash ends in zeros with probability , so among distinct values you expect to see a maximal trailing-zero length around . Track
Duplicates do not change (the same hashes the same way), so the estimate depends only on the number of distinct elements. A single estimator is high-variance, so practical versions (LogLog, HyperLogLog) average many independent estimators and correct the bias, reaching a relative error of about with registers — counting billions of distinct items in a few kilobytes.
DGIM: counting ones in a sliding window
Problem. Over a stream of bits, how many 1s occurred in the last elements? Storing the window costs bits; DGIM (Datar-Gionis-Indyk-Motwani) does it in bits with at most 50% error.
Idea. Summarise the window with buckets, each covering a range of positions and holding a count of 1s that is a power of two, . The rules:
- Each bucket stores its size (, so just the exponent — bits) and the timestamp of its most recent 1 (modulo — bits).
- Bucket sizes are non-decreasing into the past, and there are at most two buckets of each size. When a third bucket of size appears, merge the two oldest into one of size .
- Drop any bucket whose timestamp falls outside the window.
To answer a query, sum all buckets fully inside the window plus half of the oldest partially-overlapping bucket. That single halved bucket is the only source of error, which is provably at most 50% and often far less.
The unifying theme
Every sketch here follows the same recipe: pick a summary whose size is logarithmic in the stream, maintain it with -ish work per element, and accept a bounded approximation error in exchange. Sampling, membership, cardinality, and windowed counts are the building blocks that feed features into streaming models.
Python sketch
import hashlib
def trailing_zeros(x: int) -> int:
return (x & -x).bit_length() - 1 if x else 32
class FlajoletMartin:
"""Single-estimator distinct-count sketch (HyperLogLog averages many)."""
def __init__(self):
self.R = 0
def add(self, item) -> None:
h = int(hashlib.md5(str(item).encode()).hexdigest(), 16)
self.R = max(self.R, trailing_zeros(h))
def estimate(self) -> float:
return 2 ** self.R
fm = FlajoletMartin()
for user_id in stream: # duplicates are free — R only tracks distinctness
fm.add(user_id)
print("approx distinct users:", fm.estimate())
Exercise
In reservoir sampling with k = 10 slots, the t-th element is accepted with probability k/t. At roughly what stream position t does that acceptance probability fall to 0.05?
Need a hint?
Solve k/t = 0.05 for t, with k = 10.
Exercise
A Bloom filter is sized at m/n = 10 bits per element and uses the optimal number of hash functions k = (m/n)·ln2 ≈ 7. Approximately what is its false-positive rate?
Need a hint?
With optimal k, p ≈ (0.6185)^(m/n). Compute 0.6185^10.
Key takeaways
- Reservoir sampling keeps a uniform -sample in one pass, accepting element with probability — provably uniform by induction.
- Bloom filters answer membership with no false negatives and false-positive rate , minimised at .
- Flajolet-Martin / HyperLogLog estimate distinct counts from the maximum trailing-zero length, , in logarithmic space.
- DGIM counts 1s in a sliding window in bits with ≤50% error using power-of-two buckets.
Related concepts
- From Batch to Streaming: the one-pass, sublinear-memory model these sketches live in
- Concept Drift & Adaptation: sketches over sliding windows power drift detectors
- Maximum Likelihood Estimation: the estimation view behind sketch bias/variance