Efficient stream sampling for variance-optimal estimation of subset sums

DOI10.1137/10079817XMaRDI QIDQ3115872zbMATH OpenFDO

Authors Edith Cohen, N. G. Duffield, Haim Kaplan, Mikkel Thorup, C. Lund

Publication date 11 February 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/10079817X

zbMATH Keywords

reservoir samplingsampling without replacementweighted sampling

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Nonparametric estimation (62G05) Online algorithms; streaming algorithms (68W27) Communication networks in operations research (90B18)

Recommendations

• Stream sampling for variance-optimal estimation of subset sums
• On the Variance of Subset Sum Estimation
• Priority sampling for estimation of arbitrary subset sums
• Estimating Sum by Weighted Sampling
• The DLT priority sampling is essentially optimal

Cited in

(12)

• A general result for selecting balanced unequal probability samples from a stream
• Space-efficient estimation of statistics over sub-sampled streams
• Frugal Streaming for Estimating Quantiles
• Sampling from Dense Streams without Penalty
• The DLT priority sampling is essentially optimal
• Optimal Random Sampling from Distributed Streams Revisited
• Consistent subset sampling
• On the Variance of Subset Sum Estimation
• Priority sampling for estimation of arbitrary subset sums
• Stream sampling for variance-optimal estimation of subset sums
• Estimating Sum by Weighted Sampling
• Exact PPS sampling with bounded sample size

This page was built for publication: Efficient stream sampling for variance-optimal estimation of subset sums

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