The DLT priority sampling is essentially optimal

DOI10.1145/1132516.1132539zbMATH Open1301.68166OpenAlexW2036304306MaRDI QIDQ2931379FDOQ2931379

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

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

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)

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)