Communication-Efficient (Weighted) Reservoir Sampling
Lorenz Hübschle-Schneider and Peter Sanders
- Date: October 2019
We consider communication-efficient weighted and unweighted (uniform) random sampling from distributed streams presented as a sequence of mini-batches of items. We present and analyze a fully distributed algorithm for both problems. An experimental evaluation of weighted sampling on up to 256 nodes shows good speedups, while theoretical analysis promises good scaling to much larger machines.