## A. Chakrabarti, G. Cormode, and A. McGregor.
A near-optimal algorithm for computing the entropy of a stream.
In *ACM-SIAM Symposium on Discrete Algorithms (SODA)*,
2007.

We describe a simple algorithm for computing the empirical entropy of
a stream of *m* values in a single pass, using *O*(ε^{-2} log
(δ^{-1}) log^{2} *m*) words of space. Our algorithm is based upon
a novel extension of a method introduced by Alon, Matias, and Szegedy.
We show a space lower bound of Ω(ε^{-2}/log
(1/ε)), meaning that our algorithm is near optimal in terms of
its dependency on ε. This improves over previous work on this
problem. We show that generalizing to
*k*th order entropy requires close to linear space, and give additive
approximations using our algorithm.

[ bib |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*