Improving Compressed Counting
  Compressed Counting (CC) [22] was recently proposed for estimating the ath
frequency moments of data streams, where 0 < a <= 2. CC can be used for
estimating Shannon entropy, which can be approximated by certain functions of
the ath frequency moments as a -> 1. Monitoring Shannon entropy for anomaly
detection (e.g., DDoS attacks) in large networks is an important task. This
paper presents a new algorithm for improving CC. The improvement is most
substantial when a -> 1--. For example, when a = 0:99, the new algorithm
reduces the estimation variance roughly by 100-fold. This new algorithm would
make CC considerably more practical for estimating Shannon entropy.
Furthermore, the new algorithm is statistically optimal when a = 0.5.
