Communication-Efficient (Weighted) Reservoir Sampling

  • Author(s):

    Lorenz Hübschle-Schneider and Peter Sanders

  • Source:

    arXiv:1910.11069

  • 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.