Welcome to the ADMT Publication Server

Algorithms and Metrics for Processing Multiple Heterogeneous Continuous Queries

DocUID: 2008-008 Full Text: PDF

Author: Mohamed A. Sharaf, Panos K. Chrysanthis, Alexandros Labrinidis, Kirk Pruhs

Abstract: The emergence of monitoring applications has precipitated the need for Data Stream Management Systems (DSMSs) which constantly monitor incoming data feeds (through registered continuous queries), in order to detect events of interest. In this paper, we examine the problem of how to schedule multiple Continuous Queries (CQs) in a DSMS to optimize different Quality of Service (QoS) metrics. We show that, unlike traditional on-line systems, scheduling policies in DSMSs that optimize for average response time will be different from policies that optimize for average slowdown, which is a more appropriate metric to use in the presence of a heterogeneous workload. Towards this, we propose policies to optimize for the average-case performance for both metrics. Additionally, we propose a hybrid scheduling policy that strikes a fine balance between performance and fairness, by looking at both the average- and worst-case performance, for both metrics. We also show how our policies can be adaptive enough to handle the inherent dynamic nature of monitoring applications. Furthermore, we discuss how our policies can be efficiently implemented and extended to exploit sharing in optimized multi-query plans and multi-stream CQs. Finally, we experimentally show using real data that our policies consistently outperform currently used ones.

Published In: ACM Transactions in Database Systems

Volume: 33Number: 2Pages: 5.1-5.44

Year Published: 2008

Note: DOI:10.1145/1331904.1331909

Project: STREAMS,   AQSIOS Subject Area: Data Streams

Publication Type: Journal Paper

Sponsor: NSF IIS-0534531

Citation:Text Latex BibTex XML Mohamed A. Sharaf, Panos K. Chrysanthis, Alexandros Labrinidis, and Kirk Pruhs. Algorithms and Metrics for Processing Multiple Heterogeneous Continuous Queries , ACM Transactions in Database Systems (TODS), 33(2):5.1-5.44, March 2008.(DOI:10.1145/1331904.1331909)