Load shedding for shared window joins over data streams

Recently, in many applications, especially in pervasive computing and sensor network environments, data streams play a central role. The query processing technology over data streams has been widely studied. Recent researches on improving query efficiency can be divided into two groups: scheduling and load shedding. Scheduling is aimed at improving query throughput by changing the execution order of the input tuples. Load shedding is to increase the throughput of the system by discarding some fraction of the unprocessed data when system is overloaded. However, very few studies have been done by making use of these two types of technology simultaneously. In this paper, two different algorithms are presented based on the two techniques to improve the system throughput. Theoretical analysis and experiment results show that the algorithms are of high performance.