Weighted sampling without replacement from data streams

• New results for sampling in the streaming model.
• A new method of performing weighted random sampling without replacement using weighted random sampling with replacement.
• The new sampling algorithm avoids losing error when using finite precision.

Weighted sampling without replacement has proved to be a very important tool in designing new algorithms. Efraimidis and Spirakis [5] presented an algorithm for weighted sampling without replacement from data streams. Their algorithm works under the assumption of precise computations over the interval [0,1][0,1]. Cohen and Kaplan [3] used similar methods for their bottom-k sketches.Efraimidis and Spirakis ask as an open question whether using finite precision arithmetic impacts the accuracy of their algorithm. In this paper we show a method to avoid this problem by providing a precise reduction from k-sampling without replacement to k-sampling with replacement. We call the resulting method Cascade Sampling.