The sliding window model is useful for discounting stale data in data stream applications. In this model, data elements arrive continually and only the most recent N elements are used when answering queries. We consider the important problem in sliding window - computing frequency counts being not less than a user-specified threshold. We present a one-pass algorithm for dynamically computing frequency counts in sliding window over a data stream. Our algorithm employs exponential histograms to maintain the frequency of elements, and carries out compression process periodically to delete the needless elements. Once the synopsis over the most recent N elements has been constructed, our algorithm supports approximate frequency counts over the most recent M elements as long as M does not exceed N. The actual space bounds obtained on experimental data are significantly better than both the worst case guarantees of our algorithm and the observed space requirements of earlier algorithms. The analytical and experimental results show that our algorithm is accurate and effective in dynamically computing the frequency counts in sliding window
展开▼
