Estimating Entropy over Data Streams

[smart paper boy]

Abstract.
We present an algorithm for estimating entropy of data streams consisting of insertion and deletion operations using ~O(1) space.
1 1 Introduction
Recently, there has been an emergence of monitoring applications in diverse areas, including, network traf_c monitoring, network topology monitoring, sensor networks, _nancial market monitoring, web-log monitoring, etc.. In these applications, data is generated rapidly and continuously, and must be analyzed very ef_ciently, in realtime, to identify large trends, anomalies, user-de_ned exception conditions, etc.. The data streaming model [1, 12] has gained popularity as a computational model for such applications.where, incoming data (or updates) are processed very ef_ciently and in an online fashion using space that is much less than what is needed to store the data in its entirety. A data stream S is viewed as a sequence of arrivals of the form (i; v), where, i is the identity of an item that is a member of the domain f0; 1; : : : ;N