Title: Approximating the Entropy of a Stream
Speaker: Graham Cormode, AT&T Labs
Date: February 11, 2008 12:00 - 1:30 pm
Location: DyDan Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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, in small space, and with a single pass. I'll describe a simple algorithm for approximating the entropy of such a stream, and the nearly-matching lower bounds, along with some recent extensions.