Kanat TangwongsanSrikanta TirthapuraMahidol UniversityIowa State University2020-01-272020-01-272019-01-01Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.11725 LNCS, (2019), 451-46516113349030297432-s2.0-85077127039https://repository.li.mahidol.ac.th/handle/20.500.14594/50677© 2019, Springer Nature Switzerland AG. 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.Mahidol UniversityComputer ScienceMathematicsConference PaperSCOPUS10.1007/978-3-030-29400-7_32