Finding frequent items over sliding windows with constant update time

In this paper, we consider the problem of finding ε{lunate}-approximate frequent items over a sliding window of size N. A recent work by Lee and Ting (2006) [7] solves the problem by giving an algorithm that supports O (frac(1, ε{lunate})) query and update time, and uses O (frac(1, ε{lunate})) space. Their query time and memory usage are essentially optimal, but the update time is not. We give a new algorithm that supports O (1) update time with high probability while maintaining the query time and memory usage as O (frac(1, ε{lunate})).