A near-optimal algorithm for computing the entropy of a stream.

Amit Chakrabarti, Graham Cormode, Andrew McGregor

Browse the full SODA paper archive.