Data Streams Join Aggregate Algorithms Based on Compound Sliding Window

摘要

In many applications of data stream, join aggregate queries based on sliding window are a sort of queries that are widely used. All the join aggregate query algorithms in existing research works are designed for immediate continuous queries. In this paper, a join aggregate query method based on compound sliding window for periodically executed continuous queries is presented. This method organizes the basic windows in a compound sliding window into hash tables, according to their join properties, the aggregate values are computed while the join processing, the join results of compound sliding window are not saved, so the memory used by query processing is greatly reduced. An algorithm that computes the N+1th join aggregate value increment by using the Nth one is presented. Theoretical analysis and experiment result both show good time and space complexity of this incremental algorithm.