research-article

Real-time, load-adaptive processing of continuous queries over data streams

Authors:

Dhananjay Kulkarni,

Chinya V. Ravishankar,

Mitch CherniackAuthors Info & Claims

DEBS '08: Proceedings of the second international conference on Distributed event-based systems

Pages 277 - 288

https://doi.org/10.1145/1385989.1386024

Published: 01 July 2008 Publication History

Abstract

We introduce a new type of query, called a real-time continuous query (RCQ) that captures the real-time requirements of processing data streams. We develop techniques to efficiently process the RCQs in the presence of fluctuating query load and data load. We show that Rate-Monotonic scheduling is applicable to this problem domain, and show how to make this method adaptive to varying load conditions. When a set of queries becomes unschedulable due to load variations, we perform controlled input load shedding by dropping tuples using a novel feedback-based approach to decide which tuples to drop. Our work shows how to provide response time guarantees for processing RCQs, and enables making the appropriate trade-off between penalty due to missed deadlines and result accuracy. Our experiments show that our approach works very well and is usable in practice.

References

[1]

Streambase systems inc. homepage, http://www.streambase.com/.

[2]

ebay homepage, http://pages.ebay.com, 2003.

[3]

Pacific tsunami warning center, http://www.prh.noaa.gov/pr/ptwc/, 2006.

[4]

Tao project, http://www.pmel.noaa.gov/tao/, 2006.

[5]

I. T. Archive. Ita homepage, http://www.acm.org/sigcomm/ita, 2005.

[6]

R. Avnur and J. M. Hellerstein. Eddies: Continuously adaptive query processing. In Proceedings of ACM SIGMOD, volume 29. ACM, 2000.

Digital Library

[7]

B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 1--16, 2002.

Digital Library

[8]

B. Babcock, S. Babu, R. Motwani, and M. Datar. Chain: operator scheduling for memory minimization in data stream systems. In Proceedings of ACM SIGMOD, pages 253--264. ACM Press, 2003.

Digital Library

[9]

M. Cammert, J. Kramer, B. Seeger, and S. Vaupel. An approach to adaptive memory management in data stream systems. In ICDE '06: Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), page 137, Washington, DC, USA, 2006. IEEE Computer Society.

Digital Library

[10]

D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. Zdonik. Monitoring streams - A new class of data management applications. Technical Report CS-02-04, Department of Computer Science, Brown University, Feb. 2002.

[11]

S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. Shah. TelegraphCQ: Continuous dataflow processing for an uncertain world. In Proceedings of CIDR, 2003.

[12]

J. Chen, D. J. DeWitt, F. Tian, and Y. Wang. NiagaraCQ: a scalable continuous query system for Internet databases. In Proceedings of ACM SIGMOD, pages 379--390, 2000.

Digital Library

[13]

J.-Y. Chung, J. W. S. Liu, and K.-J. Lin. Scheduling periodic jobs that allow imprecise results. IEEE Trans. Comput., 39(9):1156--1174, 1990.

Digital Library

[14]

A. Deshpande. An initial study of overheads of eddies. SIGMOD Rec., 33(1):44--49, 2004.

Digital Library

[15]

M. Gardner and J. Liu. Performance of algorithms for scheduling real-time systems with overrun and overload, 1999.

[16]

B. Kao and H. Garcia-Molina. An overview of real-time database systems. pages 463--486, 1995.

Digital Library

[17]

C. M. Krishna and K. G. Shin. Real-time Systems. McGraw Hill, Reading, Massachusetts, 1997.

Digital Library

[18]

S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. In Proceedings of ICDE, 2002.

Digital Library

[19]

S. Madden, M. A. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuous queries over streams. In Proceedings of SIGMOD, 2002.

Digital Library

[20]

R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Manku, C. Olston, J. Rosenstein, and R. Varma. Query processing, resource management, and approximation in a data stream management system. In Proceedings of CIDR, 2003.

[21]

P. Seshadri, M. Livny, and R. Ramakrishnan. Sequence query processing. In Proceedings of ACM SIGMOD, pages 430--441, 1994.

Digital Library

[22]

W. K. Shih and J. W.-S. Liu. Algorithms for scheduling imprecise computations with timing constraints to minimize maximum error. IEEE Transactions on Computers, 44(3):466--471, 1995.

Digital Library

[23]

M. Sullivan and A. Heybey. Tribeca: A system for managing large databases of network traffic. In Proceedings of USENIX Annual Technical Conference, pages 13--24, 1998.

Digital Library

[24]

N. Tatbul, U. Çetintemel, S. Zdonik, M. Cherniack, and M. Stonebraker. Load shedding in a data stream manager. In vldb'2003: Proceedings of the 29th international conference on Very large data bases, pages 309--320. VLDB Endowment, 2003.

Digital Library

[25]

Traderbot. Traderbot homepage, http://traderbot.com, 2003.

[26]

S. Viglas and J. F. Naughton. Rate-based query optimization for streaming information sources. In Proceedings of SIGMOD, 2002.

Digital Library

[27]

Y. Wei, S. H. Son, and J. A. Stankovic. Rtstream: Real-time query processing for data streams. In ISORC '06: Proceedings of the Ninth IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC'06), pages 141--150, Washington, DC, USA, 2006. IEEE Computer Society.

Digital Library

Cited By

Salamun KPavić IDžapo HČuljak I(2023)Weakly Hard Real-Time Model for Control Systems: A SurveySensors10.3390/s2310465223:10(4652)Online publication date: 11-May-2023
https://doi.org/10.3390/s23104652
Patroumpas KPapadias S(2019)Trajectory-aware Load Adaption for Continuous Traffic AnalyticsProceedings of the 16th International Symposium on Spatial and Temporal Databases10.1145/3340964.3340967(70-79)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3340964.3340967
Fu CLiu QWu PLi MXue CZhao YHu JHan S(2019)Real-Time Data Retrieval in Cyber-Physical Systems with Temporal Validity and Data Availability ConstraintsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.286684231:9(1779-1793)Online publication date: 1-Sep-2019
https://doi.org/10.1109/TKDE.2018.2866842
Show More Cited By

Index Terms

Real-time, load-adaptive processing of continuous queries over data streams
1. Information systems
  1. Information systems applications

Recommendations

Continuous query processing in data streams using duality of data and queries
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data

Recent data stream systems such as TelegraphCQ have employed the well-known property of duality between data and queries. In these systems, query processing methods are classified into two dual categories -- data-initiative and query-initiative -- ...
CPU load shedding for binary stream joins

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 ofselective processing for load shedding. We allow stream tuples to be ...
Semantic load shedding for prioritized continuous queries over data streams
ISCIS'05: Proceedings of the 20th international conference on Computer and Information Sciences

A data stream management system (DSMS) has to handle high-volume and bursty data streams with large number of continuous queries. When an input rate of any data stream exceeds the system capacity, the DSMS has to shed load by dropping some fraction of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

DEBS '08: Proceedings of the second international conference on Distributed event-based systems

July 2008

377 pages

ISBN:9781605580906

DOI:10.1145/1385989

General Chair:
Roberto Baldoni
Sapienza Universitá di Roma, Italy

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE
USENIX Assoc: USENIX Assoc
IFIP: International Federation for Information Processing

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DEBS '08

Sponsor:

USENIX Assoc
IFIP

DEBS '08: Distributed Event-based Systems Conference

July 1 - 4, 2008

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 145 of 583 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
456
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Salamun KPavić IDžapo HČuljak I(2023)Weakly Hard Real-Time Model for Control Systems: A SurveySensors10.3390/s2310465223:10(4652)Online publication date: 11-May-2023
https://doi.org/10.3390/s23104652
Patroumpas KPapadias S(2019)Trajectory-aware Load Adaption for Continuous Traffic AnalyticsProceedings of the 16th International Symposium on Spatial and Temporal Databases10.1145/3340964.3340967(70-79)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3340964.3340967
Fu CLiu QWu PLi MXue CZhao YHu JHan S(2019)Real-Time Data Retrieval in Cyber-Physical Systems with Temporal Validity and Data Availability ConstraintsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.286684231:9(1779-1793)Online publication date: 1-Sep-2019
https://doi.org/10.1109/TKDE.2018.2866842
Fu CWu PLi MXue CZhao YHan S(2018)Real-Time Data Retrieval With Multiple Availability Intervals in CPS Under Freshness ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285737837:11(2743-2754)Online publication date: Nov-2018
https://doi.org/10.1109/TCAD.2018.2857378
Li GDeng CLi JZhou QWei W(2017)Deadline and Period Assignment for Update Transactions in Co-Scheduling EnvironmentIEEE Transactions on Computers10.1109/TC.2016.264520566:7(1119-1131)Online publication date: 1-Jul-2017
https://doi.org/10.1109/TC.2016.2645205
Li GDeng CLi JZhou Q(2017)A Linear Programming Approach for Deadline Assignment of Update Transactions in Co-scheduling Environment2017 14th International Symposium on Pervasive Systems, Algorithms and Networks & 2017 11th International Conference on Frontier of Computer Science and Technology & 2017 Third International Symposium of Creative Computing (ISPAN-FCST-ISCC)10.1109/ISPAN-FCST-ISCC.2017.25(285-292)Online publication date: Jun-2017
https://doi.org/10.1109/ISPAN-FCST-ISCC.2017.25
Wu CFu JZhang ZLiu C(2016)Efficient On/Off-Line Query Pre-processing for Telecom Social Streaming Data2016 IEEE 14th Intl Conf on Dependable, Autonomic and Secure Computing, 14th Intl Conf on Pervasive Intelligence and Computing, 2nd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress(DASC/PiCom/DataCom/CyberSciTech)10.1109/DASC-PICom-DataCom-CyberSciTec.2016.142(827-834)Online publication date: Aug-2016
https://doi.org/10.1109/DASC-PICom-DataCom-CyberSciTec.2016.142
Pham TChrysanthis PLabrinidis A(2016)Avoiding class warfareThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-015-0411-425:2(197-221)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s00778-015-0411-4
Han SLam KWang JRamamritham KMok A(2013)On Co-Scheduling of Update and Control Transactions in Real-Time Sensing and Control SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2012.17325:10(2325-2342)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1109/TKDE.2012.173
Wang JLam KHan SSon SMok A(2013)An effective fixed priority co-scheduling algorithm for periodic update and application transactionsComputing10.1007/s00607-012-0242-895:10-11(993-1018)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1007/s00607-012-0242-8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents