Algorithms and metrics for processing multiple heterogeneous continuous queries

Sharaf, Mohamed A., Chrysanthis, Panos K., Labrinidis, Alexandros and Pruhs, Kirk (2008) Algorithms and metrics for processing multiple heterogeneous continuous queries. ACM Transactions On Database Systems, 33 1: 5:1-5:44. doi:10.1145/1331904.1331909

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Sharaf, Mohamed A.
Chrysanthis, Panos K.
Labrinidis, Alexandros
Pruhs, Kirk
Title Algorithms and metrics for processing multiple heterogeneous continuous queries
Journal name ACM Transactions On Database Systems   Check publisher's open access policy
ISSN 0362-5915
Publication date 2008-03
Sub-type Article (original research)
DOI 10.1145/1331904.1331909
Volume 33
Issue 1
Start page 5:1
End page 5:44
Total pages 44
Place of publication New York, United States
Publisher Association for Computing Machinery
Language eng
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 article, 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 online 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.
Keyword Data stream management system
Continuous queries
Operator scheduling
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ
Additional Notes Article # 5

Document type: Journal Article
Sub-type: Article (original research)
Collections: ERA 2012 Admin Only
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 7 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 27 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 23 Oct 2011, 03:15:22 EST by Dr Mohamed Sharaf on behalf of School of Information Technol and Elec Engineering