数据流上的复合滑动窗口聚集算法

Aggregate Algorithms of Compound Sliding Window over Data Streams

基于滑动窗口的聚集查询是数据流研究领域的一个热点问题。在已有的研究工作中,聚集算法都是针对立即执行的连续查询提出的,这些算法均是当数据流新到一个元组立即计算一次聚集结果。而在实际应用中,连续查询有时采取的是周期执行方式。论文针对周期执行的连续查询提出了复合滑动窗口聚集算法,即数据流新到一个元组,将它插入到基本窗口中,当基本窗口被插满时计算一次聚集结果。给出了非增量式和增量式两种算法。理论分析和实验结果表明增量式算法具有较好的性能。

Aggregate based on Sliding window is a focus problem in data stream research.Now all the existing query processing algorithms on data streams are based on the immediately execution continuous queries.Aggregate answers are computed by these algorithms when a tuple comes.But continuous queries are based on the periodically execution manner in fact.This paper presents aggregate algorithms of compound sliding window based on the periodically execution manner.A tuple is inserted into a basic window when it comes.Aggregate answers are computed when a basic window is inserted fully.This paper presents two types algorithms,namely increment and non-increment.Theoretical analysis and experiment results show that incremental algorithms is the most efficient.