An efficient parallel algorithm for random sampling

DOI10.1016/0020-0190(89)90206-8MaRDI QIDQ1116335zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90206-8

zbMATH Keywords

CREWparallel algorithmPRAMrandom sampling

Mathematics Subject Classification ID

Combinatorial probability (60C05) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Review text

A parallel algorithm for drawing an unbiased random sample of size M from a population of N elements where \(M\leq N\) is proposed. The algorithm runs in O(log M) time on a concurrent read, exclusive write (CREW) PRAM with M processors.

Recommendations

• Efficient parallel random sampling-vectorized, cache-efficient, and online
• scientific article; zbMATH DE number 1419212
• Random sampling with a reservoir
• Parallel streaming random sampling
• An efficient algorithm for random sampling without replacement

Cites work

• An efficient algorithm for random sampling without replacement
• Correction: Parallel Merge Sort
• Development of Sampling Plans by Using Sequential (Item by Item) Selection Techniques and Digital Computers
• Faster methods for random sampling
• scientific article; zbMATH DE number 4047072 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Sorting in \(c \log n\) parallel steps
• Tight Bounds on the Complexity of Parallel Sorting
• Two efficient algorithms for random sampling without replacement

Cited in

(7)

• Weighted random sampling with a reservoir
• The probabilistic method yields deterministic parallel algorithms
• An improved deterministic algorithm for generating different many-element random samples
• Parallel streaming random sampling
• Efficient parallel random sampling-vectorized, cache-efficient, and online
• Generalized parallel sampling
• A fast algorithm for balanced sampling

This page was built for publication: An efficient parallel algorithm for random sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116335)