A. Chakrabarti, G. Cormode, and A. McGregor. A near-optimal algorithm for computing the entropy of a stream. ACM Transactions on Algorithms, 6(3), 2010.

We describe a simple algorithm for approximating the empirical entropy of a stream of m values up to a multiplicative factor of (1+ε) using a single pass, O-2 log (δ-1) logm) words of space, and O(logε-1 + log logδ-1 + loglogm) processing time per item in the stream. Our algorithm is based upon a novel extension of a method introduced by Alon, Matias, and Szegedy. This improves over previous work on this problem. We show a space lower bound of Ω(ε-2/ log2-1)), demonstrating that our algorithm is near-optimal in terms of its dependency on ε.

We show that generalizing to multiplicative-approximation of the k-th order entropy requires close to linear space for k>=1. In contrast we show that additive-approximation is possible in a single pass using only poly-logarithmic space. Lastly, we show how to compute a multiplicative approximation to the entropy of a random walk on an undirected graph.

bib | .pdf ] Back

This file was generated by bibtex2html 1.92.