Incremental Computation Of Aggregate Operators Over Sliding Windows

Abstract: Sliding Window is the most popular data model in processing data streams as it captures finite and relevant subset of an infinite stream. This paper studies different Mathematical operators used for querying and mining of data streams. The focus of our study is on operators, operating on the whole data set. These are termed as blocking operators. We have classified these operators according to their method of evaluation. An operator is termed as aggregate operator if it produces the sub-set of values satisfying some given condition. The evaluation of these operators is more complex when the query is continuous and data are changing. We present here a formal definition of incremental computation on sliding windows. We have proposed a vector model and graph abstraction to represent the sliding window and algorithms to evaluate Mathematical operators on the sliding window. The model is robust and can be applied to visualize different mathematical operators on the sliding window. We have introduced a novel concept of checkpoints in order to make the computation incremental. We present an efficient algorithm to find maximum (or minimum) on the sliding windows using the checkpoint concept. Key words: Algorithm, incremental, sliding window