The DLT priority sampling is essentially optimal

DOI10.1145/1132516.1132539MaRDI QIDQ2931379zbMATHOpenAlexFDO

Authors Mario Szegedy

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132539

zbMATH Keywords

integral formulainternet traffictelescopic sumsnetwork measurementpriority samplingsubset sum estimate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Network design and communication in computer systems (68M10) Internet topics (68M11)

Recommendations

• Priority sampling for estimation of arbitrary subset sums
• Stream sampling for variance-optimal estimation of subset sums
• Efficient stream sampling for variance-optimal estimation of subset sums
• On the Variance of Subset Sum Estimation
• Estimating Sum by Weighted Sampling

Cited in

(6)

• Efficient stream sampling for variance-optimal estimation of subset sums
• Weighted sampling without replacement from data streams
• The query complexity of estimating weighted averages
• Optimal sampling from sliding windows
• Priority sampling for estimation of arbitrary subset sums
• Space-efficient estimation of statistics over sub-sampled streams

This page was built for publication: The DLT priority sampling is essentially optimal

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