Feasible Sampling of Non-strict Turnstile Data Streams

Neta Barkay, Ely Porat, Bar Shalem

We present the first feasible method for sampling a dynamic data stream with deletions, where the sample consists of pairs $(k,C_k)$ of a value $k$ and its exact total count $C_k$.…