the streaming model
Imagine standing at the door of a stadium, counting and analyzing a river of fans pouring through one at a time, but you are only allowed a single small notebook — far too small to write down every name. You see each person exactly once, in order, and then they are gone; you can never go back and look again. The streaming model captures computation under exactly this pressure: the input is enormous and arrives as a one-pass sequence, and your working memory is tiny — much smaller than the data, often only polylog in its size.
Precisely, the data is a stream of items x1, x2, ..., xm that you process one at a time using memory s, where s is far smaller than m (think s = O((log m)^2) while m is in the billions). After each item you may update your small summary, but you cannot store the stream, and typically you get only one pass over it. Because exact answers to many questions provably require remembering too much, streaming algorithms settle for approximate, probabilistic answers and use clever summaries called sketches. The recurring trick is to keep a small randomized digest that supports the query: for example, to estimate how many DISTINCT items you saw, you do not store the items — you watch a hash-based statistic of them, which a few words of memory can track while giving a good estimate.
Streaming matters because modern data — network packets, search queries, sensor readings, clickstreams — arrives faster and larger than any machine can store, so 'just keep it all and compute later' is impossible. The model forces a sharp question: which statistics can be (approximately) computed with almost no memory? The answers are surprising and useful — counts, heavy hitters, distinct elements, quantiles — and underpin real systems in databases and networking. The honest caveats: most non-trivial streaming results are approximate and randomized (an exact, deterministic answer is often impossible in small space), the guarantees are probabilistic (correct with high probability, not certainty), and 'one pass' is a real constraint — allowing a few passes can change what is achievable.
A router sees a billion packets per minute and wants to know how many DISTINCT source IPs appeared. Storing every IP needs gigabytes. A streaming distinct-count sketch (like HyperLogLog) keeps a few kilobytes, updates on each packet in O(1), and reports an estimate within a few percent — exact storage is impossible, but a tiny sketch suffices.
One pass, tiny memory: store a sketch, not the data; answers are approximate and randomized.
In the streaming model the constraint is MEMORY (sublinear, often polylog), not just time. Most useful streaming answers are approximate and randomized because exact, deterministic answers provably need too much space. 'One pass' matters — multi-pass models can do strictly more.