Weighted Reservoir Sampling with Replacement from Multiple Data Streams
<|reference_start|>Weighted Reservoir Sampling with Replacement from Multiple Data Streams: Reservoir sampling techniques can be used to extract a sample from a population of unknown size, where units are observed sequentially. Most of attention has been placed to sampling without replacement, with only a small number of studies focusing on sampling with replacement. Specifically, to the author's knowledge, no one has explored in detail how to deal with the weighted case. In this work, we demonstrate that the results shown in Park et al. (2004) can be further generalized using similar techniques to develop a fast skip-based algorithm for weighted reservoir sampling with replacement. It is also shown that the algorithm can be adapted to be executed on multiple streams in parallel. Furthermore, we found that the algorithm is faster than standard methods when used to extract a single sample from the population in a non-streaming scenario.<|reference_end|>
@article{meligrana2024weighted,
    title={Weighted Reservoir Sampling with Replacement from Multiple Data Streams},
    author={Adriano Meligrana},
    journal={arXiv preprint arXiv:2403.20256},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.20256},
    primaryClass={cs.DS}
}