Adaptive Load Shedding for Windowed Stream Joins

Show full item record

Please use this identifier to cite or link to this item:

Title: Adaptive Load Shedding for Windowed Stream Joins
Author: Gedik, Bugra ; Wu, Kun-Lung ; Yu, Philip S. ; Liu, Ling
Abstract: We present an adaptive load shedding approach for windowed stream joins. In contrast to the conventional approach of dropping tuples from the input streams, we explore the concept of selective processing for load shedding, focusing on costly stream joins such as those over set-valued or weighted set-valued attributes. The main idea of our adaptive load shedding approach is two-fold. First, we allow stream tuples to be stored in the windows and shed excessive CPU load by performing the stream join operations, not on the entire set of tuples within the windows, but on a dynamically changing subset of tuples that are highly beneficial. Second, we support such dynamic selective processing through three forms of runtime adaptations: By adaptation to input stream rates, we perform partial processing based load shedding and dynamically determine the fraction of the windows to be processed by comparing the tuple consumption rate of join operation to the incoming stream rates. By adaptation to time correlation between the streams, we dynamically determine the number of basic windows to be used and prioritize the tuples for selective processing, encouraging CPU-limited execution of stream joins in high priority basic windows. By adaptation to join directions, we dynamically determine the most beneficial direction to perform stream joins in order to process more useful tuples under heavy load conditions and boost the utility or number of output tuples produced. Our load shedding framework not only enables us to integrate utility-based load shedding with time correlation-based load shedding, but more importantly, it also allows load shedding to be adaptive to various dynamic stream properties. Inverted indexes are used to further speed up the execution of stream joins based on set-valued attributes. Experiments are conducted to evaluate the effectiveness of our adaptive load shedding approach in terms of output rate and utility.
Type: Technical Report
Date: 2005
Relation: CERCS;GIT-CERCS-05-05
Publisher: Georgia Institute of Technology
Subject: Attributes
CPU load
Dynamic stream properties
Input streams
Load shedding
Output rate
Selective processing
Stream joins
Windowed stream joins

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
git-cercs-05-05.pdf 621.4Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record