KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel Weighted Random Sampling [in press]

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, permutation, subset sampling, and reservoir sampling. Our output sensitive algorithm for sampling with replacement also improves the state of the art for sequential algorithms.

Open Access Logo


Postprint §
DOI: 10.5445/IR/1000097067
Veröffentlicht am 08.08.2019
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2019
Sprache Englisch
Identifikator KITopen-ID: 1000097067
HGF-Programm 46.12.02 (POF III, LK 01)
Erschienen in 27th European Symposium on Algorithms, Munich/Garching, Germany, 9th - 11th September 2019
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Wadern
Serie Leibniz International Proceedings in Informatics ; 144
Vorab online veröffentlicht am 12.07.2019
Schlagworte categorical distribution, multinoulli distribution, parallel algorithm, alias method, PRAM, communication efficient algorithm, subset sampling, reservoir sampling
Nachgewiesen in arXiv
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page