A simpler and more efficient deterministic scheme for finding frequent items over sliding windows
Lap–Kei Lee, Hing‐Fung Ting · 2006
In this paper, we give a simple scheme for identifying ε-approximate frequent items over a sliding window of size n. Our scheme is deterministic and does not make any assumption on the distribution of the item frequencies. It supports O(1/ε) update and query time, and uses O(1/ε) space. It is very simple; its main data structures are just a few short queues whose entries store the position of some items in the sliding window. We also extend our scheme for variable-size window. This extended scheme uses O(1/ε log(εn)) space.