D²Sketch: Supporting Efficient Identification of Heavy Hitters Over Sliding Windows

Heavy hitters can provide an important indicator for detecting abnormal network events. Most of existing algorithms for heavy hitter identification are implemented to deal with static datasets generated within a fixed time frame, lacking the ability to handle the latest arrivals of data streams adaptively. Considering the rigid demand for accurate and fast detection of outlier events in some networks like Smart Grids, these existing algorithms are not suitable to be deployed straightforward. To this end, this paper presents a new algorithm called D²Sketch for efficient heavy hitter identification over an adaptive sliding window for flexible dataset input. D²Sketch provides a novel framework that combines the Count-Min Sketch to get the connection degree of each host, with the stream-summary structure of Space Saving algorithm to get a more accurate list of Top-K heavy hitters. Moreover, it can adjust its measurement window to the most recent datasets automatically. Extensive experimental results show that the D²Sketch algorithm outperforms the related algorithm in terms of false positive rate, ordering deviation and estimate error.