A near-optimal algorithm for estimating the entropy of a stream
Amit Chakrabarti, Graham Cormode, Andrew McGregor · ACM Transactions on Algorithms · 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 ) log m ) words of space, and O (log ϵ −1 + log log δ −1 + log log m ) processing time per item in the stream. Our algorithm is based upon a novel extension of a method introduced by Alon et al. [1999]. This improves over previous work on this problem. We show a space lower bound of Ω(ϵ −2 /log 2 (ϵ −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.