Streaming Algorithms

An introduction to streaming and probabilistic data structures: how to answer questions about data too big to store by making one pass and keeping only a small sketch, trading a bounded, tunable error for an enormous cut in memory, with concentration inequalities as the engine that keeps the error small.