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(lo...