KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel Weighted Random Sampling

Hübschle-Schneider, Lorenz; Sanders, Peter

Abstract (englisch):
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.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000097067
Veröffentlicht am 11.05.2020
Originalveröffentlichung
DOI: 10.4230/LIPIcs.ESA.2019.59
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2019
Sprache Englisch
Identifikator ISSN: 0000-2008
KITopen-ID: 1000097067
HGF-Programm 46.12.02 (POF III, LK 01)
Data Activities
Erschienen in 27th European Symposium on Algorithms, Munich/Garching, Germany, 9th - 11th September 2019. Hrsg.: M.A. Bender
Veranstaltung 27th Annual European Symposium on Algorithms (ESA 2019), Garching bei München, Deutschland, 09.09.2019 – 11.09.2019
Verlag Leibniz-Zentrum für Informatik, Wadern
Seiten Aritcle no: 59
Serie Leibniz International Proceedings in Informatics ; 144
Vorab online veröffentlicht am 12.07.2019
Schlagwörter categorical distribution, multinoulli distribution, parallel algorithm, alias method, PRAM, communication efficient algorithm, subset sampling, reservoir sampling
Nachgewiesen in Scopus
arXiv
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page