A near-optimal algorithm for estimating the entropy of a stream

DOI10.1145/1798596.1798604zbMath1300.68064OpenAlexW2104635635MaRDI QIDQ2930333

Andrew McGregor, Amit Chakrabarti, Graham Cormode

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

entropyapproximation algorithmsdata streams

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (7)

Anticoncentration and the Exact Gap-Hamming Problem ⋮ Evaluating Bayesian Networks via Data Streams ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Improved algorithms for distributed entropy monitoring ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.

This page was built for publication: A near-optimal algorithm for estimating the entropy of a stream