The Streaming Model: One Pass, Sublinear Space, Approximate Answers

A streaming algorithm reads its input once, in arrival order, and answers questions about it using memory that does not grow with the input length. That sentence contains three separate restrictions, and each one removes a technique that would otherwise be available: no second look, no reordering, no storage of the input. What remains is a small class of algorithms whose behaviour is worth understanding precisely, because the restrictions are not stylistic. They are forced by inputs that arrive continuously and are never materialised anywhere.

The model, stated precisely

The input is a sequence of updates $x_1, x_2, \dots, x_n$, each drawn from a universe $[m] = {1, \dots, m}$. In the most common formulation the update is an element identifier, and the stream implicitly defines a frequency vector $f$ where $f_i$ counts occurrences of $i$. The algorithm maintains a state $S_t = \text{update}(S_{t-1}, x_t)$, and at any point may be asked for an estimate of some function of $f$. Space is counted in bits and must be $o(n)$, usually $O(\operatorname{polylog} n)$ or $O(n^{1-\alpha})$ for a constant $\alpha$.

Randomisation is permitted, and almost always necessary. The error guarantee then has one of two shapes. An $\varepsilon$-approximation returns a value within a $1 \pm \varepsilon$ multiplicative factor of the true answer. An $(\varepsilon, \delta)$-approximation does so with probability at least $1 - \delta$ over the algorithm’s own coin flips. The distinction matters: a fixed error bound with no failure probability is a different engineering object from a bound that holds except in rare runs, and the space costs differ by a factor of $\log(1/\delta)$ in most constructions.

Two accounting choices are easy to get wrong. First, the hash functions a randomised algorithm uses must be counted in its space, even though in practice a fixed seed is compiled in and the cost is invisible. Second, the time to process one update is a real constraint; a sketch that costs $O(m)$ per element is not usable on a stream even if its memory is tiny.

Three stream types, three levels of difficulty

The same input length supports very different algorithms depending on which updates are allowed.

Model	Update	Typical difficulty	Example
Cash register (insert-only)	$f_i \mathrel{+}= 1$	easiest	log lines, click events
Turnstile (dynamic)	$f_i \mathrel{+}= \Delta$, $\Delta \in \mathbb{Z}$	hardest	network flows, retractions
Sliding window	only the last $W$ updates count	between the two	rate limits, recent traffic

Insert-only streams allow counters and monotone arguments: a value that has been seen stays seen. Turnstile streams allow arbitrary signed updates, so a frequency can rise and fall, and an algorithm cannot assume that anything it observed remains true. The turnstile model is strictly harder; several problems that cost $O(\log n)$ bits in the cash-register model require $\Omega(n)$ in the turnstile model, and others become impossible in one pass at any sublinear space.

Sliding windows replace the whole-stream function with a function of the last $W$ items. That is a different object even though the underlying data is identical: the answer must change as old items expire, so the algorithm needs a way to forget selectively. The bucket-based approach in sliding window aggregation handles this by storing timestamps inside the summary.

Order is a fourth axis. A stream that arrives in a uniformly random order is easier than one an adversary chooses, because the adversary selects which items arrive when. Sampling algorithms are correct under any arrival order, and a linear sketch is order-invariant for the same reason addition is commutative. Order sensitivity enters only through structures whose memory is bounded by recency: the sliding-window buckets below summarise the same events differently depending on where the burst sits. Statements of the form “this algorithm works on any arrival order” are therefore stronger than they look, and the analysis usually proves the order assumption explicitly.

Why exact answers cost linear space

Consider a deterministic one-pass algorithm that claims to compute the number of distinct elements exactly. Take $n$ even and consider streams of the form $A \circ B$ where $A$ and $B$ are each sequences of $n/2$ distinct elements from a universe of size $m = n$. Either $B$ is a permutation of $A$, in which case the distinct count is $n/2$, or $B$ is disjoint from $A$, in which case it is $n$.

After reading $A$, the algorithm is in some state $s(A)$. If two different sets $A \neq A’$ lead to the same state, the algorithm cannot distinguish the stream $A \circ A$ from $A’ \circ A$, yet the first has $n/2$ distinct elements and the second has close to $n$. So distinct sets must map to distinct states, and there are $\binom{m}{n/2} = 2^{\Theta(n)}$ of them. The state therefore occupies $\Omega(n)$ bits, which is the size of the input itself. The argument is a counting argument, not a cryptographic one; it applies to every deterministic algorithm and, with a little more care, to randomised ones as well.

The same shape of argument rules out exact median, exact mode, and exact sorting in one pass with sublinear space. Sorting is the clearest case: the last element read may belong at the front of the output, so an algorithm that has not retained the other $n-1$ elements cannot produce the first output element.

Approximation changes the conclusion. If a $1 \pm \varepsilon$ answer is acceptable, distinct counting becomes possible in $O(1/\varepsilon^2 + \log n)$ bits, which is the subject of HyperLogLog. The transition from impossible to cheap happens exactly at the point where the output is allowed to be wrong by a controlled amount.

What a sketch buys beyond a single answer

A sketch is a compressed representation that supports more than one query. The important structural property is mergeability: given sketches of two streams, the sketch of their concatenation can be computed from the two sketches alone, without access to either stream. For linear sketches this is just addition. If the sketch is $y = A x$ for a fixed random matrix $A$ and frequency vector $x$, then

$$ A(x + x’) = Ax + Ax’ $$

so merging two sketches costs one pass over the sketch arrays and no communication of the original data. That property is what makes sketches usable in distributed settings: each node sketches its local partition, the summaries are combined at a coordinator, and the coordinator never sees the raw events. The same property underlies linear sketches and sparse recovery, where the matrix formulation is the whole design.

Not every streaming algorithm is mergeable. Reservoir sampling is not, in general: two uniform samples of two halves of a stream cannot be combined into a uniform sample of the whole without knowing the halves’ lengths, and even then the combination is only uniform if the sampling rates are adjusted correctly. Quantile summaries are mergeable but lose accuracy on each merge unless the merge procedure is designed for it.

import hashlib

def bucket_of(key, width):
    # a deterministic hash: Python's built-in hash() is randomised per process,
    # and two sketches can only merge if they agree on where each key lands
    h = hashlib.blake2b(key, digest_size=8).digest()
    return int.from_bytes(h, 'big') % width

class SumSketch:
    """A linear sketch: merge is componentwise addition."""

    def __init__(self, width):
        self.v = [0] * width

    def update(self, key, delta=1):
        # signed updates are allowed: this is a turnstile sketch
        self.v[bucket_of(key, len(self.v))] += delta

    def merge(self, other):
        assert len(self.v) == len(other.v)
        out = SumSketch(len(self.v))
        out.v = [a + b for a, b in zip(self.v, other.v)]
        return out

The sketch above is deliberately trivial and answers nothing useful on its own; a single bucket sum cannot recover individual frequencies. It shows the shape that every linear sketch in this cluster shares: a fixed-size array, an update that adds into positions selected by a hash, and a merge that adds arrays. The interesting part of each real construction is the estimator that reads the array, and the analysis that shows the estimator’s error is small. Count-Min chooses one hash per row and reads the minimum; Count Sketch adds a sign to each bucket and reads the median.

The cost axes and how they trade

Five quantities move against each other, and no algorithm optimises all of them.

• Space. The headline number, but only meaningful together with the error guarantee. “256 bytes” without “to within 2%” is not a claim.
• Passes. One pass is the defining constraint, but some problems (graph connectivity in the turnstile model, triangle counting) are only tractable with $\log n$ passes, and the pass count is then the cost being traded.
• Accuracy. Halving $\varepsilon$ typically quadruples space for sketch-based estimators, because variance falls as $1/m$ for $m$ independent estimates.
• Update time. Per-element work must be constant or logarithmic. A sketch that requires a sort per update is not a streaming algorithm.
• Mergeability. Free for linear sketches, expensive or impossible for sampling-based ones.

The quadratic relation between accuracy and space is worth internalising early, because it sets the expectations for every estimator in this cluster. To halve the error of a HyperLogLog register array, the array must grow by a factor of four. To get an error of 1% requires on the order of ten thousand registers. This is not an implementation detail that a better constant can fix; it is the shape of the variance of an average.

Where the model misleads

The model abstracts away several things that dominate real deployments.

The input is assumed to be a sequence, but streams frequently arrive out of order relative to event time. An algorithm that computes a window over arrival order computes something different from a window over event time, and the difference is not a small perturbation when the stream is delayed. Windowed summaries in sliding window aggregation are defined over arrival order unless the implementation carries event timestamps and handles late data explicitly.

The model also assumes the algorithm controls its own randomness. When the hash seed is fixed by a configuration file, an adversary who knows the seed can construct inputs that collide deliberately. Pairwise-independent hash families, as introduced by Carter and Wegman, are the standard defence: they are cheap to evaluate and sufficient for the variance arguments that sketches rely on, without requiring cryptographic strength. A sketch built on a single fixed modulus is not the same object as one built on a randomly chosen member of a universal family.

Finally, sublinear space is a statement about asymptotics. An algorithm with $O(\log n)$ space may still allocate a few kilobytes, and at the scales where streaming algorithms are used, a few kilobytes is nothing while a constant factor of three in the update path is everything. The asymptotic ranking of two algorithms says nothing about which one is faster per element, and per-element cost is usually what determines whether a stream can be processed at line rate.