Load Shedding for Window Joins over Streams

作     者：韩东红 王国仁 肖川 周锐 

作者机构：Institute of Computer System Northeastern University Shenyang 110003 China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2007年第22卷第2期

页      面：182-189页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work is supported by the National Natural Science Foundation of China under Grant Nos. 60473074  60573089 and National Grand Fundamental Research 973 Program of China under Grant No. 2006CB303103 

主　　题：data stream window joins load shedding dual window model window resizing 

摘      要：We address several load shedding techniques over sliding window joins. We first construct a dual window architectural model including aux-windows and join-windows, and build statistics on aux-windows. With the statistics, we develop an effective load shedding strategy producing maximum subset join outputs. In order to accelerate the load shedding process, binary indexed trees have been utilized to reduce the cost on shedding evaluation. When streams have high arrival rates, we propose an approach incorporating front-shedding and rear-shedding, and find an optimal trade-off between them. As for the scenarios of variable speed ratio, we develop a plan reallocating CPU resources and dynamically resizing the windows. In addition, we prove that load shedding is not affected during the process of reallocation. Both synthetic and real data are used in our experiments, and the results show the promise of our strategies.