KIT | KIT-Bibliothek | Impressum | Datenschutz

Communication-Efficient Weighted Reservoir Sampling from Fully Distributed Data Streams

Hübschle-Schneider, Lorenz; Sanders, Peter

Abstract (englisch):
We consider weighted random sampling from distributed data streams presented as a sequence of mini-batches of items. This is a natural model for distributed streaming computation, and our goal is to showcase its usefulness. We present and analyze a fully distributed, communication-efficient algorithm for weighted reservoir sampling in this model. An experimental evaluation on up to 256 nodes (5120 processors) shows good speedups, while theoretical analysis promises further scaling to much larger machines.

Open Access Logo


Download
Originalveröffentlichung
DOI: 10.1145/3350755.3400287
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsmonat/-jahr 07.2020
Sprache Englisch
Identifikator ISBN: 978-1-4503-6935-0
KITopen-ID: 1000122361
HGF-Programm 46.12.02 (POF III, LK 01) Data Activities
Erschienen in Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
Veranstaltung 32nd Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), Online, 14.07.2020 – 16.07.2020
Verlag Association for Computing Machinery (ACM)
Seiten 543–545
Bemerkung zur Veröffentlichung Die Veranstaltung fand wegen der Corona-Pandemie als Online-Event statt. Ursprünglich in Philadelphia, PA
Vorab online veröffentlicht am 09.07.2020
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page