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

DOI10.1145/1798596.1798604MaRDI QIDQ2930333zbMATH OpenOpenAlexFDO

Authors Amit Chakrabarti, Graham Cormode, Andrew McGregor

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

approximation algorithmsdata streamsentropy

Mathematics Subject Classification ID

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

Recommendations

• A near-optimal algorithm for computing the entropy of a stream
• Estimating Entropy and Entropy Norm on Data Streams
• Estimating Entropy and Entropy Norm on Data Streams
• Estimating Entropy over Data Streams
• The Complexity of Approximating the Entropy

Cited in

(14)

• Improved algorithms for distributed entropy monitoring
• A near-optimal algorithm for computing the entropy of a stream
• Approximating entropy from sublinear samples
• scientific article; zbMATH DE number 6351507 (Why is no real title available?)
• Evaluating Bayesian networks via data streams
• Estimating Entropy and Entropy Norm on Data Streams
• Compressed counting
• Continuous monitoring of _p norms in data streams
• Nearly optimal distinct elements and heavy hitters on sliding windows
• Anticoncentration and the Exact Gap-Hamming Problem
• Estimating Entropy over Data Streams
• Estimating Entropy and Entropy Norm on Data Streams
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Towards Optimal Moment Estimation in Streaming and Distributed Models

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

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