2026-07-23T20:03:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11180 2024-03-06T10:47:39Z ddc:004 open_access

Parallel Weighted Random Sampling Hübschle-Schneider, Lorenz Sanders, Peter categorical distribution multinoulli distribution parallel algorithm alias method PRAM communication efficient algorithm subset sampling reservoir sampling Data structures for efficient sampling from a set of weighted items are an important building block of many applications. However, few parallel solutions are known. We close many of these gaps both for shared-memory and distributed-memory machines. We give efficient, fast, and practicable algorithms for sampling single items, k items with/without replacement, permutations, subsets, and reservoirs. We also give improved sequential algorithms for alias table construction and for sampling with replacement. Experiments on shared-memory parallel machines with up to 158 threads show near linear speedups both for construction and queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lorenz Hübschle-Schneider and Peter Sanders 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.59 urn:nbn:de:0030-drops-111800 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.59 eng https://creativecommons.org/licenses/by/3.0/legalcode