A Heaviest Hitters Limiting Mechanism with O(1) Time Complexity for Sliding-Window Data Streams

Abstract

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.