Streaming Algorithms & SketchesOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

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 kk elements from a stream whose length nn you do not know.

Algorithm R (Vitter):

  • Put the first kk elements directly into the reservoir.
  • For the tt-th element (t>kt > k), with probability k/tk/t replace a uniformly chosen reservoir slot with it; otherwise discard it.

Reservoir sampling: a uniform sample in one pass

incoming stream →80skipreservoir (k = 6)47612232296P(accept next) = k/t = 0.075
seen80
P(accept)=k/t0.075
swaps so far13

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 tt elements, every element seen so far is in the reservoir with probability exactly k/tk/t.

  • Base case: the first kk elements each start with probability k/k=1k/k = 1.
  • Inductive step: element t+1t{+}1 enters with probability kt+1\frac{k}{t+1} by construction. An element already in the reservoir (probability kt\frac{k}{t}) survives if either the new element is rejected, or it is accepted but evicts a different slot:
kt[(1−kt+1)⏟reject new+kt+1⋅k−1k⏟accept, evict another]=kt⋅tt+1=kt+1.\frac{k}{t}\left[\underbrace{\left(1-\frac{k}{t+1}\right)}_{\text{reject new}} + \underbrace{\frac{k}{t+1}\cdot\frac{k-1}{k}}_{\text{accept, evict another}}\right] = \frac{k}{t}\cdot\frac{t}{t+1} = \frac{k}{t+1}.

Every element, old or new, ends at kt+1\frac{k}{t+1} — a uniform sample, in O(k)O(k) space and O(1)O(1) 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

1/7

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.

python
1for t, x in enumerate(stream, start=1):
2
3 if t <= k:
4 # fill the reservoir
5 R[t-1] = x
6 continue
7
8 # accept with probability k/t
9 if random() < k / t:
10 # evict a UNIFORMLY chosen slot
11 j = randint(0, k-1)
12 R[j] = x
state
reservoir after the first 3 elements
e1slot 0
e2slot 1
e3slot 2
state
k → 3seen → 3P(in reservoir) → 1.000 eachmemory → O(k) = 3

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 k/n=0.25k/n = 0.25. 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 1/t1/t instead of k/tk/t 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 mm-bit array and kk independent hash functions. To insert xx, set the bits h1(x),…,hk(x)h_1(x),\dots,h_k(x) to 1. To query xx, report "present" only if all kk 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 kk bits.

After inserting nn elements, the probability a given bit is still 0 is (1−1m)kn≈e−kn/m\left(1-\frac{1}{m}\right)^{kn}\approx e^{-kn/m}, so the false-positive rate is

p≈(1−e−kn/m)k.p \approx \left(1 - e^{-kn/m}\right)^{k}.

For fixed mm and nn, this is minimised at

kopt=mnln⁡2,pmin⁡≈(0.5)kopt=(0.6185)m/n.k_{\text{opt}} = \frac{m}{n}\ln 2, \qquad p_{\min} \approx (0.5)^{k_{\text{opt}}} = (0.6185)^{m/n}.

Reading the formula

More bits per element (m/nm/n) shrinks the error exponentially; the optimal number of hashes is k=mnln⁡2k=\tfrac{m}{n}\ln 2. 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

1/8

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.

python
1class Bloom:
2 def __init__(self, m, k):
3 self.bits = [0] * m
4 self.m, self.k = m, k
5
6 def add(self, x):
7 for i in range(self.k):
8 self.bits[h(x, i) % self.m] = 1
9
10 def query(self, x):
11 # "absent" is always correct;
12 # "present" may be a false positive
13 return all(self.bits[h(x, i) % self.m]
14 for i in range(self.k))
15
16def fp_rate(m, k, n):
17 # after n inserts
18 return (1 - exp(-k * n / m)) ** k
state
bit array (m = 16, 0 set)
00
01
02
03
04
05
06
07
08
09
010
011
012
013
014
015

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 (1−e−kn/m)k(1 - e^{-kn/m})^k across twelve values of kk at ~10 bits per element, and finds a bottom so flat that every kk 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 O(n)O(n); Flajolet-Martin (FM) does it in O(log⁡n)O(\log n) bits.

Idea. Hash each element to a uniformly random bit string. Let r(x)r(x) be the number of trailing zeros in h(x)h(x). A random hash ends in ≥r\geq r zeros with probability 2−r2^{-r}, so among dd distinct values you expect to see a maximal trailing-zero length around log⁡2d\log_2 d. Track

R=max⁡x∈streamr(x),d^=2R.R = \max_{x \in \text{stream}} r(x), \qquad \widehat{d} = 2^{R}.

Duplicates do not change RR (the same xx 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 1.04/m1.04/\sqrt{m} with mm registers — counting billions of distinct items in a few kilobytes.

Deep dive
HyperLogLog: Registers, Harmonic Means & Range Corrections
Includes runnable notebook

DGIM: counting ones in a sliding window

Problem. Over a stream of bits, how many 1s occurred in the last NN elements? Storing the window costs NN bits; DGIM (Datar-Gionis-Indyk-Motwani) does it in O(log⁡2N)O(\log^2 N) 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, 2j2^j. The rules:

  • Each bucket stores its size (2j2^j, so just the exponent jj — O(log⁡log⁡N)O(\log\log N) bits) and the timestamp of its most recent 1 (modulo NN — O(log⁡N)O(\log N) 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 2j2^j appears, merge the two oldest into one of size 2j+12^{j+1}.
  • 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.

Deep dive
DGIM: A Worked Bucket Trace
Includes runnable notebook

The unifying theme

Every sketch here follows the same recipe: pick a summary whose size is logarithmic in the stream, maintain it with O(1)O(1)-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

Python
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?

10205.00400
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 kk-sample in one pass, accepting element tt with probability k/tk/t — provably uniform by induction.
  • Bloom filters answer membership with no false negatives and false-positive rate (1−e−kn/m)k\left(1-e^{-kn/m}\right)^k, minimised at k=mnln⁡2k=\tfrac{m}{n}\ln 2.
  • Flajolet-Martin / HyperLogLog estimate distinct counts from the maximum trailing-zero length, d^=2R\widehat d = 2^{R}, in logarithmic space.
  • DGIM counts 1s in a sliding window in O(log⁡2N)O(\log^2 N) bits with ≤50% error using power-of-two buckets.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Streaming Algorithms & SketchesOptimization for MLML in PracticeFrom Batch to StreamingConcept Drift & AdaptationMaximum Likelihood Estima…HyperLogLogDGIM: Counting Ones in a …