Computing the entropy of a stream, December 2006. AT&T Labs; Bell Labs; DyDAn Center.

Recently there has been much interest in using empirical entropy and related measures to analyze behaviour in networks, and identify anomalies. At the heart of this is the basic problem of, given a sequence of tokens, how to efficiently compute the empirical entropy of the sequence efficiently, in small space, and with a single pass.

I'll describe some work with Amit Chakrabarti and Andrew McGregor on a simple algorithm for computing the entropy of such a stream, and the corresponding lower bounds. I'll also discuss extensions to the `graph entropy', and why higher order entropy is harder to approximate.

bib | .pdf ] Back

This file was generated by bibtex2html 1.92.