Weighted random sampling with a reservoir

DOI10.1016/J.IPL.2005.11.003MaRDI QIDQ1045927zbMATH OpenOpenAlexWikidataFDO

Authors Pavlos S. Efraimidis, P. G. Spirakis

Publication date 18 December 2009

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

Full work available at URL https://doi.org/10.1016/j.ipl.2005.11.003

zbMATH Keywords

randomized algorithmsdata streamsparallel algorithmsreservoir samplingweighted random sampling

Mathematics Subject Classification ID

Randomized algorithms (68W20) Parallel algorithms in computer science (68W10)

Recommendations

• Random sampling with a reservoir
• Weighted sampling without replacement from data streams
• Reservoir-sampling algorithms of time complexity O ( n (1 + log( N / n )))
• Practical algorithms for generating a random ordering of the elements of a weighted set
• An efficient algorithm for random sampling without replacement

Cites work

• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• An Efficient Method for Weighted Sampling without Replacement
• An efficient parallel algorithm for random sampling
• Data streams: algorithms and applications.
• Faster methods for random sampling
• Random sampling in cut, flow, and network design problems
• Random sampling in residual graphs
• Random sampling with a reservoir
• Reservoir-sampling algorithms of time complexity O ( n (1 + log( N / n )))

Cited in

(20)

• scientific article; zbMATH DE number 7378732 (Why is no real title available?)
• scientific article; zbMATH DE number 2101371 (Why is no real title available?)
• Weighted sampling without replacement from data streams
• Ancestral Gumbel-top-\(k\) sampling for sampling without replacement
• Markov chain Monte Carlo sampling using a reservoir method
• Parallel streaming random sampling
• A survey on concept drift adaptation
• Random sampling with a reservoir
• A stratified reservoir sampling algorithm in streams and large datasets
• Random generation of \(k\)-interactive capacities
• Practical algorithms for generating a random ordering of the elements of a weighted set
• Online estimation of individual-level effects using streaming shrinkage factors
• Design of 3D anisotropic Voronoi porous structure driven by stress field
• Independent range sampling, revisited
• Parallel Weighted Random Sampling
• Heterogeneous subset sampling
• Parallel Weighted Random Sampling
• Space-efficient estimation of statistics over sub-sampled streams
• A family of unsupervised sampling algorithms
• Remarks on some misconceptions about unequal probability sampling without replacement

This page was built for publication: Weighted random sampling with a reservoir

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