A Heaviest Hitters Limiting Mechanism with O(1) Time Complexity for Sliding-Window Data Streams
In this work we address the problem of identifying and limiting the heaviest hitters in a sliding-window data stream. We propose the first, to our knowledge, exact (i.e., not approximate) algorithm which achieves O(1) with high probability time complexity in both update and query operations. Additionally, it tracks the first and last item ;of any itemset in the window in O(1) time complexity as well as the lightest hitters with no additional computational costs. These properties allow us to efficiently implement a mechanism to limit the heaviest hitters by evicting them from or not allowing them in the window. We describe the algorithms and data structure which implement this functionality, we explain how they can be used to accomplish the goal of limiting the heaviest hitters and perform experiments to produce quantitative results to support our theoretical arguments.
heaviest hitters data streams mining sliding window on-line algorithms