  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$. Our algorithms are for both Strict Turnstile data
streams and the most general Non-strict Turnstile data streams, where each
element may have a negative total count. Our method improves by an order of
magnitude the known processing time of each element in the stream, which is
extremely crucial for data stream applications. For example, for a sample of
size $O(\epsilon^{-2} \log{(1/\delta)})$ in Non-strict streams, our solution
requires $O((\log\log(1/\epsilon))^2 + (\log\log(1/\delta)) ^ 2)$ operations
per stream element, whereas the best previous solution requires
$O(\epsilon^{-2} \log^2(1/\delta))$ evaluations of a fully independent hash
function per element. Here $1-\delta$ is the success probability and $\epsilon$
is the additive approximation error.
  We achieve this improvement by constructing a single data structure from
which multiple elements can be extracted with very high success probability.
The sample we generate is useful for calculating both forward and inverse
distribution statistics, within an additive error, with provable guarantees on
the success probability. Furthermore, our algorithms can run on distributed
systems and extract statistics on the union or difference between data streams.
They can be used to calculate the Jaccard similarity coefficient as well.
