基于滑动窗口的数据流连续J-A查询的处理方法  

Sliding Window Based Method for Processing Continuous J-A Queries on Data Streams

作　　者：王伟平[1] 李建中[1] 张冬冬[1] 郭龙江[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《软件学报》2006年第4期740-749,共10页Journal of Software

基　　金：国家自然科学基金;黑龙江省自然科学基金~~

摘　　要：数据流滑动窗口连接聚集连续查询(简记J-A查询)是经常使用的一类查询.这类查询的直观处理方法是创建查询操作树,以流水线的方式计算查询结果.这种方法需要在主存中保存滑动窗口连接的结果,查询处理的主存空间开销为Ο(α×β),其中α,β为参加连接两个滑动窗口的大小.在数据流的查询处理中,内存是最重要的计算资源.提出了两种滑动窗口J-A连续查询处理算法——IC算法和TC算法,使得查询处理的空间开销降为Ο(α+β).理论分析和实验结果表明,所提出的算法具有更高的效率.Sliding window join aggregation continuous queries （J-A queries for short） are often used in data stream applications. The intuitive method for processing these queries is to construct steaming operator tree and execute the tree in pipeline. The space cost of this method is O（α×β）, where a and fl are the sizes of two sliding windows respectively. To reduce the requirement of memory, which is the most expensive resource in data stream query processing system, two novel sliding window J-A continuous query processing algorithms IC and TC are presented in this paper, whose space cost are both O（α＋β）. Theoretical analysis and experimental results show that the algorithms are more effective.

关 键 词：数据流 滑动窗口 连接聚集 连续查询 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]