The firehose: data you see once and cannot store
The last guide put you in the shoes of an online algorithm, deciding now without seeing the future. The streaming model keeps that one-pass spirit but adds a second, brutal constraint: not only does the future arrive one item at a time, you also cannot keep the past. Picture network packets crossing a router, search queries hitting a server, or sensor readings from a billion devices — a sequence so long that storing all of it is out of the question. You get to read each item once, in order, and then it is gone forever.
The headline resource here is not time but space. We measure how many bits of working memory the algorithm holds at once, and the dream is sublinear space — much smaller than the stream length, ideally something like O(log n) bits, or polylogarithmic in the number of distinct items. If the stream has a trillion entries, an honest streaming algorithm might use only a few kilobytes. That is the whole game: keep a tiny, cleverly-chosen summary in your hand while the river roars past, and answer the question from the summary alone.
Morris's counter: counting to a billion in a byte
Start with the gentlest possible question: just count the items as they stream by. A plain counter needs about log n bits to reach n — to count to a billion you need roughly 30 bits. Tiny already, but it is the perfect place to meet the streaming mindset, because we can do dramatically better if we accept an approximate count. The trick is the Morris counter, and it is gorgeous.
Instead of storing the count n, store an exponent X meant to track roughly log n. We keep X, not n. On each new item we do not always increment — we flip a biased coin and increment X only with probability 1 / 2^X. So when X is small, incrementing is easy and frequent; as X grows, increments get exponentially rarer. To read off an estimate of the true count we report 2^X - 1. Because X only ever climbs to about log n, storing X needs only about log log n bits — to count to a billion, roughly 5 bits, a single byte with room to spare.
init X = 0
on each item:
with probability 1 / 2^X: X = X + 1
estimate of count = 2^X - 1Why is 2^X - 1 the right thing to report? The clean way to see it is through the expected value: if you track the random variable 2^X, a short calculation shows that after n items its expectation is exactly n + 1, so 2^X - 1 is an unbiased estimator of n. That is the honest part — on average it is spot on. The catch is variance: a single Morris counter is noisy, and any one run can be off. The standard fix is to run several independent counters and average them, which shrinks the spread; this is a Monte Carlo answer, fast and tiny but only probably close, not guaranteed exact.
Heavy hitters: who shows up a lot, with a handful of slots
A more practical question: which items appear often? Think trending search terms, or the IP addresses flooding a server. We want every item occurring more than, say, a 1/k fraction of the time — the heavy hitters. Storing a count for every distinct item could need huge memory. The Misra-Gries algorithm finds the frequent ones with just k - 1 counters, no matter how many distinct items stream by.
- Keep at most k - 1 labeled counters, all starting empty. For each arriving item: if it already has a counter, add one to it.
- Otherwise, if there is a free counter slot, claim it for this item and set its count to one.
- Otherwise (no slot free), decrement every one of the k - 1 counters by one; any counter that hits zero is released for future items.
- At the end, the surviving labels are your candidate heavy hitters; their stored counts under-estimate true frequency, but never by more than n/k.
Why does this work? Each global decrement step throws away k items at once (one real arrival plus k - 1 charged against existing counts), and you can only do that floor(n/k) times in a stream of length n. So any single item can lose at most n/k from its true count — which means a genuine heavy hitter, appearing more than n/k times, cannot be wiped out and must survive with a positive counter. The flip side is the honest limitation: some survivors may be impostors that never truly crossed the threshold, so Misra-Gries guarantees it catches every heavy hitter but may also report a few false ones. A second pass, if you can afford it, filters those out.
Sketches: hashing many items into a small grid
The deepest streaming idea is the sketch: a small, fixed-size data structure that summarizes the stream so that approximate answers can be read straight from it. The star example is the count-min sketch, which estimates the frequency of any item you ask about, using a grid of counters and a family of hash functions. It leans on the same workhorse you met way back in the randomized-algorithms rung: universal hashing, where a randomly chosen hash spreads items so that collisions are rare and, crucially, analyzable.
Picture a grid with d rows and w columns of counters, all starting at zero, with one independent hash function per row mapping items to a column. To process an item, hash it once per row and add one to each of the d cells it lands in. To query an item's count, hash it the same way and read those d cells — then report the minimum of them. Each cell holds the true count of its item plus whatever other items collided into the same cell, so every cell over-estimates; taking the smallest of d independent over-estimates is your best, tightest guess. Total memory is just d times w counters, completely independent of how many distinct items appeared.
Here is the honest accounting. Each cell adds only extra mass from collisions, so it never under-counts — the minimum is therefore an upper bound on the truth, and the error is one-sided. Universal hashing makes the expected collision noise in any one row small (on the order of total-mass / w), and a Markov-inequality argument turns that into a per-row failure probability; the d independent rows then drive the chance of all rows being bad down exponentially, much as a Chernoff-style argument would. Pick w around e/epsilon and d around ln(1/delta), and you get: with probability at least 1 - delta, every estimate overshoots the truth by at most epsilon times the stream's total count. Small grid, tunable error, no per-item storage.
Counting the distinct: how many different things flew by?
One last classic, and a beautiful one: how many distinct items did the stream contain? Not the total length — the number of different values. Exact answers need memory proportional to the count of distinct items, which can be enormous, so we estimate. The core idea behind distinct-element counting is to hash each item to a random-looking real number in [0, 1] and simply remember the smallest hash value ever seen.
The intuition is delightfully simple. If you drop m distinct values uniformly at random into [0, 1], they tend to space out, and the smallest of them sits near 1/(m + 1). Repeated items hash to the same number, so they never push the minimum lower — only distinct values matter, exactly the quantity we want. So if the smallest hash you ever saw is some value v, then 1/v - 1 is a sensible estimate of the number of distinct items. One real number in memory, and duplicates are automatically ignored.
What streaming really buys, and what it costs
Step back and the shared recipe is clear. Every method here trades an exact, certain answer for an approximate, probably-correct one, and that single concession is what unlocks sublinear space against problems whose exact versions provably cannot fit. The tools doing the heavy lifting are the randomized machinery you already own from earlier rungs: hashing to scatter items predictably, the linearity of expectation to pin down what an estimator means on average, and concentration bounds to argue the estimate rarely strays far. Streaming is not a new bag of tricks so much as those tricks aimed at a single, severe memory budget.
Be precise about the guarantees, because the easy misreading is dangerous. A count-min over-estimate of "at most epsilon times the total" is a worst-case bound that holds with high probability — not a promise about any single query in isolation, and the rare failure event genuinely can happen. Morris and distinct-counting give unbiased estimators, meaning correct on average over the randomness, which is not the same as correct on your particular run; that is why averaging many copies is not optional polish but the thing that makes the variance small enough to rely on. And like any randomized method, these are honest only relative to their assumptions — chiefly that the hash functions behave randomly enough, which universal hashing is carefully designed to deliver.
Finally, hold the boundary clearly. Streaming sketches shine for additive, aggregate questions — counts, frequencies, distinct totals, heavy hitters — where small per-item error washes out in a summary. They are the wrong tool when you need an exact set membership, a precise median, or to reconstruct the data itself, because the information was thrown away on purpose. Knowing which questions a tiny summary can and cannot answer is the real skill, and it carries straight into the next frontiers: the same beyond-worst-case, approximate-but-good-enough mindset reappears in parameterized algorithms and in local search, where structure and good-enough answers again beat brute exactness.