A near-optimal algorithm for estimating the entropy of a stream
A near-optimal algorithm for estimating the entropy of a stream
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 …