Succinct Sampling on Streams

Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo

A streaming model is one where data items arrive over long period of time, either one item at a time or in bursts. Typical tasks include computing various statistics over a sliding…