Home | deutsch  | Legals | Data Protection | Sitemap | KIT

Communication-Efficient (Weighted) Reservoir Sampling

Communication-Efficient (Weighted) Reservoir Sampling
Author(s):

Lorenz Hübschle-Schneider and Peter Sanders

Links:
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.