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

MaRDI QIDQ2934611zbMATH OpenFDO

Authors Amit Chakrabarti, Graham Cormode, Andrew McGregor

Publication date 18 December 2014

Mathematics Subject Classification ID

Random walks on graphs (05C81) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• A near-optimal algorithm for estimating 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)

• Sketching information divergences
• Hierarchical sampling from sketches: Estimating functions over data streams
• Arthur-Merlin streaming complexity
• A near-optimal algorithm for estimating the entropy of a stream
• scientific article; zbMATH DE number 6351507 (Why is no real title available?)
• Estimating Entropy and Entropy Norm on Data Streams
• Optimal sampling from sliding windows
• The entropy of backwards analysis
• Compressed counting
• Estimating Entropy over Data Streams
• Estimating Entropy and Entropy Norm on Data Streams
• Range (Rényi) entropy queries and partitioning
• Range entropy queries and partitioning
• Exponential time improvement for min-wise based algorithms

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

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