A Gentle Introduction to Streaming Algorithms

What can you actually compute about a stream of data that is too large to store, and that you only ever see once? I look at the streaming model through the lens of counting problems: finding heavy hitters with the Misra–Gries algorithm, and counting distinct elements with the CVM algorithm of Chakraborty, Vinodchandran, and Meel (a sampling-based method simple enough to appear in an undergraduate textbook). I explain (ε, δ)-approximation guarantees, use interactive demos to show the algorithms running live, and place all of it inside a forty-year history and in practical systems like Apache DataSketches.