Load shedding for window joins over streams

Dong Hong Han*, Guo Ren Wang, Chuan Xiao, Rui Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)182-189
Number of pages8
JournalJournal of Computer Science and Technology
Volume22
Issue number2
DOIs
Publication statusPublished - Mar 2007
Externally publishedYes

Keywords

  • Data stream
  • Dual window model
  • Load shedding
  • Window joins
  • Window resizing

Fingerprint

Dive into the research topics of 'Load shedding for window joins over streams'. Together they form a unique fingerprint.

Cite this