###
DOI:
Journal of Software:2006.17(4):740-749

基于滑动窗口的数据流连续J-A查询的处理方法
王伟平,李建中,张冬冬,郭龙江
(哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001;哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001;黑龙江大学,计算机科学与技术学院,黑龙江,哈尔滨,150080)
Sliding Window Based Method for Processing Continuous J-A Queries on Data Streams
WANG Wei-Ping,LI Jian-Zhong,ZHANG Dong-Dong,GUO Long-Jiang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3020   Download 3063
Received:April 27, 2004    Revised:July 11, 2005
> 中文摘要: 数据流滑动窗口连接聚集连续查询(简记J-A查询)是经常使用的一类查询.这类查询的直观处理方法是创建查询操作树,以流水线的方式计算查询结果.这种方法需要在主存中保存滑动窗口连接的结果,查询处理的主存空间开销为O(α×β),其中(,(为参加连接两个滑动窗口的大小.在数据流的查询处理中,内存是最重要的计算资源.提出了两种滑动窗口J-A连续查询处理算法--IC算法和TC算法,使得查询处理的空间开销降为Ο(α+β).理论分析和实验结果表明,所提出的算法具有更高的效率.
中文关键词: 数据流  滑动窗口  连接聚集  连续查询
Abstract: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 α and β 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.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60273082, 60473075 (国家自然科学基金); the Natural Science Foundation of Heilongjiang Province of China under Grant No.zjg03-05 (黑龙江省自然科学基金) Supported by the National Natural Science Foundation of China under Grant Nos.60273082, 60473075 (国家自然科学基金); the Natural Science Foundation of Heilongjiang Province of China under Grant No.zjg03-05 (黑龙江省自然科学基金)
Foundation items:
Reference text:

王伟平,李建中,张冬冬,郭龙江.基于滑动窗口的数据流连续J-A查询的处理方法.软件学报,2006,17(4):740-749

WANG Wei-Ping,LI Jian-Zhong,ZHANG Dong-Dong,GUO Long-Jiang.Sliding Window Based Method for Processing Continuous J-A Queries on Data Streams.Journal of Software,2006,17(4):740-749