Parallel streaming random sampling
From MaRDI portal
Abstract: This paper investigates parallel random sampling from a potentially-unending data stream whose elements are revealed in a series of element sequences (minibatches). While sampling from a stream was extensively studied sequentially, not much has been explored in the parallel context, with prior parallel random-sampling algorithms focusing on the static batch model. We present parallel algorithms for minibatch-stream sampling in two settings: (1) sliding window, which draws samples from a prespecified number of most-recently observed elements, and (2) infinite window, which draws samples from all the elements received. Our algorithms are computationally and memory efficient: their work matches the fastest sequential counterpart, their parallel depth is small (polylogarithmic), and their memory usage matches the best known.
Recommendations
Cites work
- scientific article; zbMATH DE number 2119720 (Why is no real title available?)
- Continuous sampling from distributed streams
- Efficient parallel random sampling-vectorized, cache-efficient, and online
- Optimal sampling from sliding windows
- Random sampling with a reservoir
- Sketching asynchronous data streams over sliding windows
- Weighted random sampling with a reservoir
Cited in
(7)- Parallel sampling from big data with uncertainty distribution
- Partial order aware concurrency sampling
- Generalized parallel sampling
- Parallel Weighted Random Sampling
- Parallel streams of linear random numbers in the spectral test
- An efficient parallel algorithm for random sampling
- Efficient parallel random sampling-vectorized, cache-efficient, and online
This page was built for publication: Parallel streaming random sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297571)
