Finding heavy hitters over the sliding window of a weighted data stream

Abstract

We study the problem of identifying items with heavy weights in the sliding window of a weighted data stream. We give a deterministic algorithm that solves the problem within error bound ε, uses space and supports query and update times. Here, R is the maximum item weight. We also show that the space can be reduced substantially in practice by showing for any c∈>∈0, we can construct an -space algorithm, which returns correct answers provided that the ratio between the total weights of any two adjacent sliding windows is not greater than c. We also give a randomized algorithm that solves the problem with success probability 1∈-∈δ using space where D is the number of distinct items in the data stream. © 2008 Springer-Verlag Berlin Heidelberg.