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² 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 kth 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.