Our work on parallel algorithms for streaming random sampling has been accepted to Europar 2019. This presents parallel methods for a fundamental problem — reservoir sampling from a stream, and its variants, including sliding window. The algorithms are work-efficient and have low-depth (i.e. they are highly parallel). Parallelizing the “seemingly sequential” steps of these algorithms has some twists to it. Please check out our paper ( will post the final version soon) — joint work with Kanat Tangwongsan of Mahidol University, Thailand.
