• Articles • Previous Articles     Next Articles

Load Shedding for Window Joins over Streams

Dong-Hong Han, Guo-Ren Wang, Chuan Xiao, and Rui Zhou   

  1. Institute of Computer System, Northeastern University, Shenyang 110004, China
  • Received:2006-04-28 Revised:2006-12-26 Online:2007-03-10 Published:2007-03-10

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.



[1] Babcock B, Babu S, Datar M \it et al. \rm Models and issues in data stream systems. In -\it Proc. Principles of Database Systems $($PODS$)$}, June 2002.

[2] Abadi D, Carney D \it et al. \rm Aurora: A new model and architecture for data stream management. -\it VLDB Journal}, 2003, 12(2): 120--139.

[3] Daniel J Abadi, Yanif Ahmad, M Balazinska \it et al. \rm The design of the Borealis stream processing engine. In -\it Proc. 2nd Conf. Innovative Data Systems Research}, CA, USA, January 2005, pp.227--289.

[4] The STREAM Group. STREAM: The Stanford stream data manager. -\it IEEE Data Engineering Bulletin}, March 2003, 26(1):19--26.

[5] Chen J, DeWitt D J, Tian F \it et al. \rm NiagaraCQ: A scalable continous query system for Internet databases. In -\it Proc. ACM SIGMOD Int. Conf. Management of Data}, Dallas, USA, 2000, pp.379--390.

[6] Hellerstein J M, Franklin M J, Chandrasekaran S \it et al. \rm Adaptive query processing: Technology in evolution. -\it IEEE Data Engineering Bulletin}, 2000, 23(2): 7--18.

[7] Kang J, Naughton J F, Viglas S D. Evaluating window joins over unbounded streams. In -\it Proc. 2003 Int. Conf. Data Engineering}, Mar. 2003, pp.341--352.

[8] Ayad A M, Naughton J F. Static optimization of conjunctive queries with sliding windows over infinite streams. In -\it Proc. ACM SIGMOD Conf.}, Paris, France, June 2004, pp.419--430.

[9] Das A, Gehrke J, Riedewald M. Approximate join processing over data streams. In -\it Proc. 2003 ACM SIGMOD Conf.}, San Diego, June 2003, pp.40--51.

[10] Xie J, Yang J, Chen Y. On joining and caching stochastic streams. In -\it Proc. 2005 ACM SIGMOD Conf.}, Baltimore, Maryland, USA, June 2005, pp.359--370.

[11] Srivastava U, Widom J. Memory-limited execution of windowed stream joins. In -\it Proc. 30th Int. Conf. Very Large Data Bases}, 2004.

[12] Fenwich P M. A new data structure for cumulative frequency tables. -\it Software --Practice and Experience}, Mar. 1994, 24(30): 327--336.

[13] Han D, Xiao C, Zhou R \it et al. \rm Load shedding for Window Joins over data streams. In -\it Proc. Conf. Web-Age Information Management}, Hong Kong, June 2006, pp.397--409.

[14] Baldocchi D, Wilson K \it et al. \rm Half-hourly measurements of CO$_2$, water vapor, and energy exchange using the Eddy covariance technique from walker branch watershed, Tennessee, 1995--1998, http://cdiac.esd.ornl.gov/ftp/ameriflux/ data/us-sites/walker-branch/.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[2] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[3] Tiziana Calamoneri, Saverio Caminiti, and Rossella Petreschi. A General Approach to {\it\bfseries L$($h,k$)$}-Label Interconnection Networks[J]. , 2008, 23(4 ): 652 -659 .
[4] Yong-Xuan Lai, Yi-Long Chen, and Hong Chen. PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks[J]. , 2008, 23(6 ): 957 -972 .
[5] Liu-Xin Zhang (张柳新), Member, CCF, Ming-Tao Pei (裴明涛), Member, CCF and Yun-De Jia (贾云得), Senior Member, CCF. Multiview Visibility Estimation for Image-Based Modeling[J]. , 2011, 26(6): 1000 -1010 .
[6] Wu Yang Guo-Wei Shen, Wei Wang, Liang-Yi Gong, Miao Yu, Guo-Zhong Dong. Anomaly Detection in Microblogging via Co-Clustering[J]. , 2015, 30(5): 1097 -1108 .
[7] Chun-Meng Kang, Lu Wang, Yan-Ning Xu, Xiang-Xu Meng, Yuan-Jie Song. Adaptive Photon Mapping Based on Gradient[J]. , 2016, 31(1): 217 -224 .
[8] Jing-Ya Zhou, Jian-Xi Fan, Cheng-Kuan Lin, Bao-Lei Cheng. A Cost-Efficient Approach to Storing Users' Data for Online Social Networks[J]. Journal of Computer Science and Technology, 2019, 34(1): 234 -252 .
[9] Meng-Ke Yuan, Long-Quan Dai, Dong-Ming Yan, Li-Qiang Zhang, Jun Xiao, Xiao-Peng Zhang. Fast and Error-Bounded Space-Variant Bilateral Filtering[J]. Journal of Computer Science and Technology, 2019, 34(3): 550 -568 .
[10] Hui-Si Wu, Meng-Shu Liu, Lu-Lu Yin, Ping Li, Zhen-Kun Wen, Hon-Cheng Wong. Automatic Video Segmentation Based on Information Centroid and Optimized SaliencyCut[J]. Journal of Computer Science and Technology, 2020, 35(3): 564 -575 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved