HEE-Sketch: an Efficient Sketch for Sliding-Window Frequency Estimation over Skewed Data Streams

Frequency estimation over sliding window has become a critical problem in data stream applications. Sketch is a widely used solution for frequency estimation, which can be successfully implement on hardware. The key metrics of sketches are accuracy, speed, and memory usage. However, existing sketches cannot achieve high accuracy, high speed and using limited memory at the same time for sliding window queries over skewed data streams. In this paper, we present the Hierarchical Elastic Exponential Sketch (HEE-sketch) to tackle the problem. For sliding-window frequency estimation, our HEE-sketch can achieve high accuracy and high speed when using limited memory. Extensive experimental results on real-world datasets show that with the same memory footprint, the accuracy of the HEE-sketch is improved up to 12.4 times, while the speed is improved up to 4.47 times, compared with the ECM-sketch, the state-of-the-art sliding-window sketch model.