The DLT priority sampling is essentially optimal

DOI10.1145/1132516.1132539MaRDI QIDQ2931379zbMATH OpenOpenAlexFDO

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)

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

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)