Streaming Algorithms

Counting in the Data Firehose

A deep dive into approximation algorithms for massive data streams,
featuring the elegant CVM algorithm for counting distinct elements.

Based on: Chakraborty, Vinodchandran, and Meel. "Distinct Elements in Streams: An Algorithm for the (Text) Book." ESA 2022.

Act I

The Streaming World

Why can't we just store everything?

The Data Firehose

Imagine you're an engineer at Hotstar during an IPL final...

The Challenge
  • Network packets: Millions per second at a router
  • Click streams: Every user interaction on a major website
  • IoT sensors: Temperature, pressure, motion across thousands of devices
  • Financial transactions: Stock trades, payment processing
The Constraints
  • One pass: Data arrives once and is gone forever
  • Small memory: Can't store the entire stream
  • Real-time: Must answer queries instantly

The Streaming Model

Definition: Data Stream

A data stream is a sequence \(\langle a_1, a_2, \ldots, a_m \rangle\) where:

  • Each \(a_i \in [n] = \{1, 2, \ldots, n\}\) is an element from a universe
  • Elements arrive one at a time
  • We can only process each element once (no random access)
Goal

Compute statistics about the stream using space \(O(\text{polylog}(m, n))\) — exponentially less than storing everything!

Key trade-off: We sacrifice exactness for space efficiency. We compute approximate answers with high probability.

A Sampler of Streaming Problems

Here's a taste of what we can solve efficiently in the streaming model:

Problem Question Application
Heavy Hitters Which items appear most frequently? Trending hashtags, DDoS detection
Quantiles What's the median? 95th percentile? Latency monitoring, salary analysis
Frequency Moments How "spread out" is the data? Entropy estimation, anomaly detection
Distinct Elements How many unique items? Unique visitors, cardinality estimation

Heavy Hitters: Misra-Gries in 3 Minutes

Problem

Find all elements that appear more than \(m/k\) times in a stream of length \(m\).

Misra-Gries Algorithm (1982)
Initialize: Empty dictionary D with at most k-1 entries

For each element e in stream:
  if e in D: D[e] += 1
  else if |D| < k-1: D[e] = 1
  else:
    for each key in D: D[key] -= 1
    Remove all keys with count 0

Return: Keys in D
Space: \(O(k \log m)\)  |  Guarantee: Never misses a heavy hitter!

Interactive: Misra-Gries Demo

Misra-Gries Heavy Hitters

2 10 4

k−1 = 3 slots to track heavy hitters

Comma-separated numbers. n is set from how many values you provide.
Processed: 0 / 100
k = 4 (slots: 3)
Press Play or Step to begin.

The \((\varepsilon, \delta)\)-Approximation Framework

The common thread across all streaming algorithms:

Definition: \((\varepsilon, \delta)\)-Approximation

An algorithm provides an \((\varepsilon, \delta)\)-approximation for quantity \(Q\) if:

$$\Pr\left[ (1-\varepsilon)Q \leq \hat{Q} \leq (1+\varepsilon)Q \right] \geq 1 - \delta$$

where \(\hat{Q}\) is the algorithm's estimate.

\(\varepsilon\) = Accuracy

How close are we to the true answer?
Smaller \(\varepsilon\) = more accurate.

\(\delta\) = Confidence

How likely is the guarantee to hold?
Smaller \(\delta\) = more confident.

Typical setting: \(\varepsilon = 0.01\) (1% error), \(\delta = 0.01\) (99% confidence)

Act II

Deep Dive: Counting Distinct Elements

The \(F_0\) problem and the elegant CVM algorithm

The Distinct Elements Problem

Problem: \(F_0\) Estimation

Given a stream \(\langle a_1, a_2, \ldots, a_m \rangle\) with elements from \([n]\),
estimate \(F_0\) = the number of distinct elements in the stream.

The Distinct Elements Problem

Problem: \(F_0\) Estimation

Given a stream \(\langle a_1, a_2, \ldots, a_m \rangle\) with elements from \([n]\),
estimate \(F_0\) = the number of distinct elements in the stream.

Why is this hard?

The naïve approach: Store all elements seen so far.

Space needed: \(O(F_0 \cdot \log n)\) bits — potentially \(O(n)\)!

Can we do exponentially better?

Spoiler: Yes! The CVM algorithm uses only \(O\left(\frac{1}{\varepsilon^2} \log \frac{1}{\delta} \cdot (\log n + \log m)\right)\) bits.

Core Idea: Sampling

Key Insight

If we pick every ball in a bin with probability \(p\) and end up with \(k\) balls in our bucket, then \(k/p\) is a good estimate of the number of balls in the bin.

80 0.30

NaiveSampler

Algorithm: NaiveSampler
Input: Stream \(\mathcal{D} = \langle a_1, a_2, \ldots, a_m \rangle\), probability \(p\)
Initialize: \(\mathcal{B} \leftarrow \emptyset\)
For \(i = 1\) to \(m\):
  With probability \(p\), \(\mathcal{B} \leftarrow \mathcal{B} \cup \{a_i\}\)
Return: \(|\mathcal{B}| / p\)
0.50
Bucket \(\mathcal{B}\):
Problem

Repeated elements inflate \(|\mathcal{B}|\) — elements appearing more often are more likely to be sampled!

The Fix: Throw It Away First

Algorithm: Sampler (Fixed)
Input: Stream \(\mathcal{D} = \langle a_1, a_2, \ldots, a_m \rangle\), probability \(p\)
Initialize: \(\mathcal{B} \leftarrow \emptyset\)
For \(i = 1\) to \(m\):
  \(\mathcal{B} \leftarrow \mathcal{B} \setminus \{a_i\}\) // throw it away
  With probability \(p\), \(\mathcal{B} \leftarrow \mathcal{B} \cup \{a_i\}\)
Return: \(|\mathcal{B}| / p\)
0.50
Bucket \(\mathcal{B}\):
Observation

Each distinct element \(x\) is in \(\mathcal{B}\) with probability exactly \(p\), independent of how many times it appeared.

Fixed-Rate Sampling: Analysis

Idea

Sample each element with probability \(p\). If we see \(|S|\) distinct elements in our sample,
estimate \(F_0 \approx |S| / p\).

Analysis: Let \(X_i = 1\) if the \(i\)-th distinct element is sampled.

  • \(\mathbb{E}[|S|] = p \cdot F_0\)
  • By Chernoff bounds, if \(p \cdot F_0\) is large enough, \(|S|/p\) is concentrated around \(F_0\)
The Problem

To get a \((1 \pm \varepsilon)\)-approximation, we need \(p \cdot F_0 = \Omega(1/\varepsilon^2)\).

But we don't know \(F_0\) in advance — that's what we're trying to compute!

  • If \(p\) is too small: sample might be empty
  • If \(p\) is too large: sample overflows our memory

The Fix: Adaptive Sampling

Key Insight

Start with \(p = 1\) (keep everything). When the sample gets too large, subsample by half and halve \(p\).

The Invariant

At all times, every distinct element seen so far is in our sample independently with probability \(p\).

Why does subsampling preserve the invariant?

  • Before subsampling: each distinct element in sample w.p. \(p\)
  • Subsampling: keep each element w.p. \(1/2\)
  • After: each distinct element in sample w.p. \(p/2\) ✓

This is the essence of the CVM algorithm (Chakraborty-Vinodchandran-Meel, ESA 2022).

The CVM Algorithm

Algorithm: CVM Distinct Elements
Input: Stream \(\langle a_1, \ldots, a_m \rangle\), buffer size \(s\)
Initialize: Buffer \(X \leftarrow \emptyset\), probability \(p \leftarrow 1\)

For each element \(a\) in stream:
  if \(a \in X\): remove \(a\) from \(X\) // Re-roll the dice
  if random() \(< p\): add \(a\) to \(X\) // Keep with prob p

  while \(|X| \geq s\): // Buffer full? Subsample!
    \(X \leftarrow\) subsample(\(X\), 1/2)
    \(p \leftarrow p/2\)

Return: \(|X| / p\)
That's it! The entire algorithm is about 10 lines. No hash functions, no complex data structures.

A Subtle Point: Why Remove First?

When element \(a\) arrives and \(a \in X\), why do we remove it before possibly re-adding?

The Issue

If we just kept \(a\) when it's already in \(X\), the probability that \(a\) is in \(X\) would depend on how many times we've seen \(a\).

This breaks the independence property!

The Fix

By always "re-rolling" — removing and then adding with probability \(p\) — we ensure:

Each distinct element is in \(X\) with probability exactly \(p\), independent of history.

This is the key to the simple analysis!

Interactive: CVM Algorithm Demo

CVM Distinct Element Counter

Stream (remaining):

Buffer X (max size s):

p (prob)
1
|X|
0
Estimate
0
True F₀
?
Click "Step" to process elements one by one, or "Run All" to see the final result.

The Analysis: Overview

We need to prove two things:

Theorem (CVM, 2022)

With buffer size \(s = O\left(\frac{1}{\varepsilon^2} \log \frac{1}{\delta}\right)\), the CVM algorithm:

  1. Never overflows: The buffer size stays below \(s\) (except momentarily)
  2. Is accurate: With probability \(\geq 1 - \delta\), the estimate \(\hat{F}_0 = |X|/p\) satisfies: $$(1 - \varepsilon)F_0 \leq \hat{F}_0 \leq (1 + \varepsilon)F_0$$

Key tools:

  • The invariant: each distinct element is in \(X\) independently w.p. \(p\)
  • Chernoff bounds for concentration
  • Union bound over failure events

The Invariant

Lemma (The Key Invariant)

At all times during the algorithm, for the current values of \(X\) and \(p\):

Each distinct element seen so far is in \(X\) independently with probability \(p\).

Proof by induction:

  • Base: Initially, \(X = \emptyset\) and \(p = 1\). Vacuously true.
  • New element \(a\) arrives (not seen before):
    We add \(a\) to \(X\) with probability \(p\). Independence preserved. ✓
  • Repeated element \(a\) arrives:
    Remove \(a\) from \(X\), then add with probability \(p\).
    Result: \(a\) is in \(X\) with probability \(p\), independent of history. ✓
  • Subsampling:
    Each element in \(X\) kept with probability \(1/2\), and \(p \leftarrow p/2\).
    New probability: \(p \cdot (1/2) = p/2\). Independence preserved by independence of coin flips. ✓

The Accuracy Guarantee

Given the invariant, \(|X|\) is the sum of \(F_0\) independent Bernoulli(\(p\)) random variables.

\(\mathbb{E}[|X|] = p \cdot F_0\)

Chernoff Bound

For sum of independent Bernoulli r.v.s with mean \(\mu\):

$$\Pr[|X - \mu| > \varepsilon \mu] < 2\exp\left(-\frac{\varepsilon^2 \mu}{3}\right)$$

At the end, \(\mu = p \cdot F_0\). We want the estimate \(|X|/p\) to be within \((1 \pm \varepsilon)F_0\).

This happens when \(|X|\) is within \((1 \pm \varepsilon) \cdot p \cdot F_0\).

Failure probability: \(2\exp\left(-\frac{\varepsilon^2 \cdot p \cdot F_0}{3}\right)\)

If \(p \cdot F_0 \geq \frac{3}{\varepsilon^2} \ln(2/\delta)\), failure probability \(\leq \delta\). ✓

Why the Buffer Doesn't Overflow

We need \(p \cdot F_0\) to be large enough for accuracy. But if it's too large, the buffer overflows!

Key Observation

After subsampling, \(\mathbb{E}[|X|] = p \cdot F_0\).

The buffer size \(s\) is chosen so that with high probability, \(|X|\) stays close to its expectation.

If \(s = c \cdot \frac{1}{\varepsilon^2} \log(1/\delta)\) for suitable constant \(c\):

  • When \(|X| \geq s\), we subsample
  • After subsampling, \(\mathbb{E}[|X|] = s/2\)
  • By Chernoff, \(|X|\) unlikely to immediately overflow again

A union bound over all \(O(\log m)\) possible values of \(p\) gives the final guarantee.

The Complete Picture

Theorem (Complete Statement)

The CVM algorithm with buffer size

$$s = O\left(\frac{1}{\varepsilon^2} \log\frac{1}{\delta} + \log n\right)$$

uses \(O(s \cdot (\log n + \log m))\) bits of space and returns an estimate \(\hat{F}_0\) such that with probability at least \(1 - \delta\):

$$(1 - \varepsilon)F_0 \leq \hat{F}_0 \leq (1 + \varepsilon)F_0$$
Why This Is Remarkable
  • No hash functions needed (unlike Flajolet-Martin, HyperLogLog)
  • Proof uses only Chernoff bounds — accessible to undergraduates!
  • Near-optimal space complexity

Accuracy Across Multiple Runs

Monte Carlo Simulation of CVM

Each dot represents one run of CVM. The horizontal band shows the \((1 \pm \varepsilon)\) range.

Act III

The Big Picture

Context, applications, and what's next

The Research Landscape

The distinct elements problem has a rich 40-year history:

Year Algorithm Key Innovation
1983 Flajolet-Martin Hash + count trailing zeros
1996 AMS (Alon-Matias-Szegedy) Frequency moments framework
2007 HyperLogLog Near-optimal, practical
2010 Kane-Nelson-Woodruff Optimal space lower bound
2022 CVM Simple + teachable + near-optimal

CVM doesn't improve the space bound, but it simplifies the algorithm and proof dramatically. Donald Knuth called it "a real gem."

Streaming in the Wild

Where are these algorithms actually used?

HyperLogLog
  • Redis: PFADD, PFCOUNT commands
  • BigQuery: APPROX_COUNT_DISTINCT
  • Druid: Cardinality aggregation
  • Presto: approx_distinct()
Count-Min Sketch
  • Network monitoring: Traffic analysis
  • NLP: Word frequency estimation
  • Databases: Query optimization
Apache DataSketches

Open-source library implementing streaming algorithms: HLL, KLL (quantiles), Theta (set operations), Frequent Items, and more.

datasketches.apache.org

Connections Outward

Streaming algorithms connect to many areas of TCS:

Communication Complexity

Lower bounds for streaming often come from communication complexity.

Example: \(F_0\) needs \(\Omega(\log n)\) bits — proved via indexing!

Sketching & Dimensionality Reduction

Random projections, JL lemma, compressed sensing — all related ideas.

Property Testing

Testing properties with sublinear samples. Related query models.

Online Algorithms

Making irrevocable decisions with limited information.

What's Still Open?

Streaming is an active research area. Some open directions:

Multi-Pass Algorithms

What if we can make 2 or 3 passes over the data? Can we do better?

Sliding Windows

Only count elements from the last \(W\) time steps. The "forgetting" makes things harder!

Distributed Streams

Data arrives at multiple sites. How do we coordinate with minimal communication?

Adversarial Streams

What if the stream is chosen adversarially based on our random bits? Differential privacy helps!

Summary

Key Takeaways
  1. The streaming model captures real constraints: one pass, limited memory, real-time.
  2. Approximate answers with high probability are often good enough — and achievable!
  3. The CVM algorithm counts distinct elements using just sampling + adaptive thresholding.
  4. The analysis uses only Chernoff bounds — undergraduate-accessible!
  5. Space complexity: \(O\left(\frac{1}{\varepsilon^2} \log \frac{1}{\delta} \cdot \log n\right)\) — exponentially better than storing everything.

References:

  • Chakraborty, Vinodchandran, Meel. "Distinct Elements in Streams: An Algorithm for the (Text) Book." ESA 2022.
  • Knuth. "The CVM Algorithm for Estimating Distinct Elements in Streams." 2024.
  • Muthukrishnan. "Data Streams: Algorithms and Applications." NOW Publishers, 2005.

Questions?

Let's discuss!

Slides available at: [your URL here]

Jupyter notebook with implementations: streaming_algorithms.ipynb