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

parallel algorithmrandom samplingPRAMCREW

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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)

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