Class-based continuous query scheduling for data streams

ABSTRACT

Wireless sensor networks link the physical and digital worlds enabling both surveillance as well as scientific exploration. In both cases, on-line detection of interesting events can be accomplished with continuous queries (CQs) in a Data Stream Management System (DSMS). However, the quality-of-service requirements of detecting these events are different for different monitoring applications. The CQs for detecting anomalous events (e.g., fire, flood) have stricter response time requirements over CQs which are for logging and keeping statistical information of physical phenomena. In this work, we are proposing the Continuous Query Class (CQC) scheduler, a new scheduling policy which employs two-level scheduling that is able to handle different ranks of CQ classes. It provides the lowest response times for classes of critical CQs, while at the same time keeping reasonable response times for the other classes down the rank. We have implemented CQC in the AQSIOS prototype DSMS and evaluated it against existing scheduling policies under different workloads.

REFERENCES

• 1: D. J. Abadi, D. Carney, U. Çetintemel, M. Cherniack, C. Convey, S. Lee, M. Stonebraker, N. Tatbul, and S. Zdonik. Aurora: a new model and architecture for data stream management. The VLDB Journal, 12(2):120--139, 2003.
• 2: A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar, K. Ito, R. Motwani, U. Srivastava, and J. Widom. Stream: The stanford data stream management system. Technical Report 2004--20, Stanford InfoLab, 2004.
• 3: B. Babcock, S. Babu, M. Datar, and R. Motwani. Chain: Operator scheduling for memory minimization in data stream systems. In SIGMOD, 2003.
• 4: B. Babcock, S. Babu, M. Datar, R. Motwani, and D. Thomas. Operator scheduling in data stream systems. The VLDB Journal, 13(4):846--860, 2004.
• 5: D. Carney, U. Çetintemel, A. Rasin, S. Zdonik, M. Cherniack, and M. Stonebraker. Operator scheduling in a data stream manager. In VLDB, 2003.
• 6: S. Kim, S. Pakzad, D. Culler, J. Demmel, G. Fenves, S. Glaser, and M. Turon. Health monitoring of civil infrastructures using wireless sensor networks. IPSN, 2007.
• 7: T. Liu, C. M. Sadler, P. Zhang, and M. Martonosi. Implementing software on resource-constrained mobile sensors: experiences with impala and zebranet. In ACM MobiSys, 2004.
• 8: H. Qu and A. Labrinidis. Preference-aware query and update scheduling in web-databases. In ICDE, 2007.
• 9: B. Schroeder, M. Harchol-Balter, A. Iyengar, and E. Nahum. Achieving class-based qos for transactional workloads. In ICDE, 2006.
• 10: M. A. Sharaf, P. K. Chrysanthis, A. Labrinidis, and K. Pruhs. Efficient scheduling of heterogeneous continuous queries. In VLDB, 2006.
• 11: M. A. Sharaf, P. K. Chrysanthis, A. Labrinidis, and K. Pruhs. Algorithms and metrics for processing multiple heterogeneous continuous queries. ACM Transactions on Database Systems, 2008.
• 12: R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler. An analysis of a large scale habitat monitoring application. In ACM SenSys, 2004.
• 13: Y. Wei, S. H. Son, and J. A. Stankovic. Rtstream: Real-time query processing for data streams. In ISORC, 2006.
• 14: Zigbee specification 053474r06, version 1.0, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
continuous queries, data stream management system, operator scheduling, priority, user-centric