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

data streamsparallel algorithmsrandomized algorithmsreservoir samplingweighted random sampling

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• 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

(23)

• Markov chain Monte Carlo sampling using a reservoir method
• Online estimation of individual-level effects using streaming shrinkage factors
• Space-efficient estimation of statistics over sub-sampled streams
• A family of unsupervised sampling algorithms
• Parallel streaming random sampling
• Heterogeneous subset sampling
• Random sampling with a reservoir
• Reservoir-sampling algorithms of time complexity O ( n (1 + log( N / n )))
• scientific article; zbMATH DE number 2101371 (Why is no real title available?)
• Practical algorithms for generating a random ordering of the elements of a weighted set
• Weighted sampling without replacement from data streams
• Ancestral Gumbel-top-k sampling for sampling without replacement
• Practical low-dimensional halfspace range space sampling
• Parallel Weighted Random Sampling
• A stratified reservoir sampling algorithm in streams and large datasets
• Independent range sampling, revisited
• A survey on concept drift adaptation
• Parallel Weighted Random Sampling
• Random generation of k-interactive capacities
• Remarks on some misconceptions about unequal probability sampling without replacement
• Design of 3D anisotropic Voronoi porous structure driven by stress field
• Range (Rényi) entropy queries and partitioning
• Sampling via Rejection-Free Partial Neighbor Search

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)