Anomaly-free incremental output in stream processing

ABSTRACT

Continuous queries enable alerts, predictions, and early warning in various domains such as health care, business process monitoring, financial applications, and environment protection. Currently, the consistency of the result cannot be assessed by the application, since only the query processor has enough internal information to determine when the output has reached a consistent state. To our knowledge, this is the first paper that addresses the problem of consistency under the assumptions and constraints of a continuous query model. In addition to defining an appropriate consistency notion, we propose techniques for guaranteeing consistency. We implemented the proposed techniques in our existing stream engine, and we report on the characteristics of the observed performance. As we show, these methods are practical as they impose only a small overhead on the system.

REFERENCES

• 1: D. J. Abadi, Y. Ahmad, M. Balazinska, U. Cetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. S. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. Zdonik. The Design of the Borealis Stream Processing Engine. In CIDR, Asilomar, CA, January 2005.
• 2: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 3: D. Agrawal , A. El Abbadi , A. Singh , T. Yurek, Efficient view maintenance at data warehouses, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.417-427, May 11-15, 1997, Tucson, Arizona, United States
• 4: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 5: R. S. Barga, J. Goldstein, M. H. Ali, and M. Hong. Consistent streaming through time: A vision for event stream processing. In CIDR, pages 363--374, 2007.
• 6: S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah. Telegraphcq: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
• 7: M. Cherniack, H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, Y. Xing, and S. Zdonik. Scalable Distributed Stream Processing. In CIDR, Asilomar, CA, 2003.
• 8: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 9: Practical Lineage Tracing in Data Warehouses, Proceedings of the 16th International Conference on Data Engineering, p.367, February 28-March 03, 2000
• 10: Shawn R. Jeffery , Gustavo Alonso , Michael J. Franklin , Wei Hong , Jennifer Widom, A Pipelined Framework for Online Cleaning of Sensor Data Streams, Proceedings of the 22nd International Conference on Data Engineering, p.140, April 03-07, 2006 [doi>10.1109/ICDE.2006.8]
• 11: Theodore Johnson , S. Muthukrishnan , Vladislav Shkapenyuk , Oliver Spatscheck, A heartbeat mechanism and its application in gigascope, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Hua-Gang Li , Songting Chen , Junichi Tatemura , Divyakant Agrawal , K. Selçuk Candan , Wang-Pin Hsiung, Safety guarantee of continuous join queries over punctuated data streams, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. S. Manku, C. Olston, J. Rosenstein, and R. Varma. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.
• 14: R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. S. Manku, C. Olston, J. Rosenstein, and R. Varma. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.
• 15: V. Raman, A. Deshpande, and J. M. Hellerstein. Using state modules for adaptive query processing. In ICDE, 2003.
• 16: Jun Rao , Sangeeta Doraiswamy , Hetal Thakkar , Latha S. Colby, A deferred cleansing method for RFID data analytics, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 17: Utkarsh Srivastava , Jennifer Widom, Flexible time management in data stream systems, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055596]
• 18: Nesime Tatbul , Uğur Çetintemel , Stan Zdonik , Mitch Cherniack , Michael Stonebraker, Load shedding in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.309-320, September 09-12, 2003, Berlin, Germany
• 19: Peter A. Tucker , David Maier , Tim Sheard , Leonidas Fegaras, Exploiting Punctuation Semantics in Continuous Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.555-568, March 2003 [doi>10.1109/TKDE.2003.1198390]
• 20: Ying Xing , Stan Zdonik , Jeong-Hyon Hwang, Dynamic Load Distribution in the Borealis Stream Processor, Proceedings of the 21st International Conference on Data Engineering, p.791-802, April 05-08, 2005 [doi>10.1109/ICDE.2005.53]
• 21: Yue Zhuge , Héctor García-Molina , Joachim Hammer , Jennifer Widom, View maintenance in a warehousing environment, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.316-327, May 22-25, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms

Keywords:
consistency, stream processing