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 trafficnetwork measurementpriority samplingsubset sum estimatetelescopic sums

Mathematics Subject Classification ID

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

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

(7)

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

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)