Communication-Efficient (Weighted) Reservoir Sampling

  • Autor:

    Lorenz Hübschle-Schneider und Peter Sanders

  • Quelle:


  • Datum: Oktober 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.