Communication-Optimal Parallel Reservoir Sampling
| dc.contributor.author | Winter, Christian | |
| dc.contributor.author | Sichert, Moritz | |
| dc.contributor.author | Birler, Altan | |
| dc.contributor.author | Neumann, Thomas | |
| dc.contributor.author | Kemper, Alfons | |
| dc.contributor.editor | König-Ries, Birgitta | |
| dc.contributor.editor | Scherzinger, Stefanie | |
| dc.contributor.editor | Lehner, Wolfgang | |
| dc.contributor.editor | Vossen, Gottfried | |
| dc.date.accessioned | 2023-02-23T13:59:52Z | |
| dc.date.available | 2023-02-23T13:59:52Z | |
| dc.date.issued | 2023 | |
| dc.description.abstract | When evaluating complex analytical queries on high-velocity data streams, many systems cannot run those queries on all elements of a stream. Sampling is a widely used method to reduce the system load by replacing the input with a representative yet manageable subset. For unbounded data, reservoir sampling generates a fixed-size uniform sample independent of the input cardinality. However, the collection of reservoir samples itself can already be a bottleneck for high-velocity data.In this paper, we introduce a technique that allows fully parallelizing reservoir sampling for many-core architectures. Our approach relies on the efficient combination of thread-local samples taken over chunks of the input without necessitating communication during the sampling phase and with minimal communication when merging. We show how our efficient merge guarantees uniform random samples while allowing data to be distributed over worker threads arbitrarily. Our analysis of this approach within the Umbra database system demonstrates linear scaling along the available threads and the ability to sustain high-velocity workloads. | en |
| dc.identifier.doi | 10.18420/BTW2023-27 | |
| dc.identifier.isbn | 978-3-88579-725-8 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/40332 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e.V. | |
| dc.relation.ispartof | BTW 2023 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-331 | |
| dc.subject | Reservoir Sampling | |
| dc.subject | Parallel Sampling | |
| dc.subject | Stream Processing | |
| dc.title | Communication-Optimal Parallel Reservoir Sampling | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 578 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 567 | |
| gi.conference.date | 06.-10. März 2023 | |
| gi.conference.location | Dresden, Germany |
Dateien
Originalbündel
1 - 1 von 1