Faster Heavy Hitters on Sliding Windows

Sliding window measurement is required by network functionalities such as load balancing, traffic engineering and intrusion detection. This work focuses on two fundamental problems -- identifying Heavy Hitters (HH) and Hierarchical Heavy Hitters (HHH) over sliding windows. We introduce two rigorously analyzed algorithms for the HH and HHH problems and perform an extensive evaluation over three real Internet packet traces. We demonstrate speedups of up to x14 for HH, X273 for HHH as well as similar accuracy compared to previous approaches. Furthermore, our HHH algorithm is the first to perform updates in constant time over a sliding window.