License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.59
URN: urn:nbn:de:0030-drops-111800
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11180/
Go to the corresponding LIPIcs Volume Portal

Hübschle-Schneider, Lorenz ; Sanders, Peter

Parallel Weighted Random Sampling

pdf-format:
LIPIcs-ESA-2019-59.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{hbschleschneider_et_al:LIPIcs:2019:11180,
  author =	{Lorenz H{\"u}bschle-Schneider and Peter Sanders},
  title =	{{Parallel Weighted Random Sampling}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{59:1--59:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11180},
  URN =		{urn:nbn:de:0030-drops-111800},
  doi =		{10.4230/LIPIcs.ESA.2019.59},
  annote =	{Keywords: categorical distribution, multinoulli distribution, parallel algorithm, alias method, PRAM, communication efficient algorithm, subset sampling, reser}
}

Keywords: categorical distribution, multinoulli distribution, parallel algorithm, alias method, PRAM, communication efficient algorithm, subset sampling, reser
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019
Supplementary Material: The code and scripts used for our experiments are available under the GPLv3 at https://github.com/lorenzhs/wrs.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI