A Hybrid Algorithm for Accurate Stream Entropy Estimation

Entropy estimation plays an important role in many network tasks, in particular, anomaly detection. Accurate estimation of entropy demands large memory. In this paper, we propose a novel hybrid algorithm that processes items with different frequencies separately. For items with frequency higher than a given threshold, counters are used while for items with lower frequency, the technique introduced by Alon, Matias and Szegedy is applied. We analyze the error and variance bounds of the estimations generated by this hybrid algorithm, proved to be more accurate than the pure random algorithm, at the cost of no significant increase in space complexity. As demonstrated by experiments, this entropy estimation may be used to detect traffic anomaly resulted from different types of attacks.