Dynamically Computing Approximate Frequency Counts in Sliding Window over Data Stream

摘要

This paper presents two one-pass algorithms for dynamically computing frequency counts in sliding window over a data stream-computing frequency counts exceeding user-specified threshold ε. The first algorithm constructs sub-windows and deletes expired sub-windows periodically in sliding window, and each sub-window maintains a summary data structure. The first algorithm outputs at most 1/ε + 1 elements for frequency queries over the most recent N elements. The second algorithm adapts multiple levels method to deal with data stream. Once the sketch of the most recent N elements has been constructed, the second algorithm can provides the answers to the frequency queries over the most recent n(n≤N) elements. The second algorithm outputs at most 1/ε+2 elements. The analytical and experimental results show that our algorithms are accurate and effective.