Research On Load Shedding Technology Based On Sliding Window Over Data Streams

The rapid development of data stream applications promote the research on data stream management systems. Sliding window aggregation queries and join queries over data streams are widely used in data stream management systems, carrying out continuous queries over data streams and producing real time query results are the main functions of these queries. When the arrival rate of data stream over the bearing capacity of the system resources, the performance of system will appear the phenomenon of degradation and even paralysis. To resolve the overload problem of the sytems when the data's arrival rate reaches its peak, load shedding technology is an effective way.At the basis of depth analysis over the key problems of data stream load shedding technology, three load shedding algorithms based on sliding window queries over data streams are given. The theoretical analysis and experiments show that the algorithms are effective and efficient for dealing with the load shedding problems over data streams. The main contributions of the papers'research work are summarized as following.Firstly, by analyzing and researching the relationship among the sliding window aggregation queries in continuous query networkof data streams. A load shedding strategy and algorithm based on the random sampling over the window is given.Secondly, by combining with the practical application background, the semantic which can express the importance of a single data stream tuple is introduced into the load shedding algorithm for sliding window aggregaion queries over data streams. A storage structure of sliding window over data streams which named semi-hash table(SHT) is designed. The data tuples which have different importance are mapped to different tuple lists.By dropping the relatively unimportant tuples when carrying out the load shedding strategy, making the tuples which involved in the sliding window aggregation query operations over data streams have greater importance.Lastly, by analyzing the existing load shedding algorithms for sliding window join queries over data streams. A load shedding algorithm which taking into account both the distribution of join property values and the importance semantic of data stream tuples is given. It maked up the deficiencies of the existing load shedding algorithms which only taking the distribution of join property values into account and enhanced the practicality of the algorithm.