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




Remous-Aris Koutsiamanis;Pavlos S. Efraimidis

Key Words

Mining ; Heaviest hitters ; Data streams ; Sliding window ; On-Line algorithms



Volume or Term/Year and Month of Publication

14卷1期(2013 / 01 / 01)

Page #

117 - 126

Content Language


English 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.

Topic Category 基礎與應用科學 > 資訊科學