Adaptive stream resource management using Kalman Filters

ABSTRACT

To answer user queries efficiently, a stream management system must handle continuous, high-volume, possibly noisy, and time-varying data streams. One major research area in stream management seeks to allocate resources (such as network bandwidth and memory) to query plans, either to minimize resource usage under a precision requirement, or to maximize precision of results under resource constraints. To date, many solutions have been proposed; however, most solutions are ad hoc with hard-coded heuristics to generate query plans. In contrast, we perceive stream resource management as fundamentally a filtering problem, in which the objective is to filter out as much data as possible to conserve resources, provided that the precision standards can be met. We select the Kalman Filter as a general and adaptive filtering solution for conserving resources. The Kalman Filter has the ability to adapt to various stream characteristics, sensor noise, and time variance. Furthermore, we realize a significant performance boost by switching from traditional methods of caching static data (which can soon become stale) to our method of caching dynamic procedures that can predict data reliably at the server without the clients' involvement. In this work we focus on minimization of communication overhead for both synthetic and real-world streams. Through examples and empirical studies, we demonstrate the flexibility and effectiveness of using the Kalman Filter as a solution for managing trade-offs between precision of results and resources in satisfying stream queries.

REFERENCES

• 1: D. Abadi , D. Carney , U. Çetintemel , M. Cherniack , C. Convey , C. Erwin , E. Galvez , M. Hatoun , A. Maskey , A. Rasin , A. Singer , M. Stonebraker , N. Tatbul , Y. Xing , R. Yan , S. Zdonik, Aurora: a data stream management system, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872855]
• 2: A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, R. Motwani, I. Nishizawa, U. Srivastava, D. Thomas, R. Varma, and J. Widom. STREAM: The stanford stream data manager. IEEE Data Engineering Bulletin, 26:19--26, March 2003.
• 3: Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543642]
• 4: B. Babcock, S. Babu, M. Datar, R. Motwani, and D. Thomas. Operator scheduling in data stream systems. Technical report, Stanford University, CA, USA, October 2003.
• 5: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 6: Brian Babcock , Mayur Datar , Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams, Proceedings of the 20th International Conference on Data Engineering, p.350, March 30-April 02, 2004
• 7: S. Babu, U. Srivastava, and J. Widom. Exploiting k-constraints to reduce memory overhead in continuous queries over data streams. Technical report, Stanford Univesity, CA, USA, November 2003.
• 8: Aggelos Bletsas, Evaluation of Kalman Filtering for Network Time Keeping, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.289, March 23-26, 2003
• 9: R. F. Boisvert, B. Miller, R. Pozo, K. Remington, J. Hicklin, C. Moler, and P. Webb. JAMA: A java matrix package.
• 10: R. G. Brown. Introduction to Random Signal Analysis and Kalman Filtering. Wiley, New York, NY, USA, 1983.
• 11: A. Bulut and A. K. Singh. SWAT: Hierarchical stream summarization in large networks. In Proceedings of the ICDE Intl. Conf. on Data Engineering, pages 303--314, Bangalore, India, March 2003.
• 12: S. Chandrasekaran. Telegraph CQ: Continuous dataflow processing for an uncertain world. In Proceedings of the CIDR Conf. on Innovative Data Systems Research, Asilomar, CA, USA, January 2003.
• 13: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 14: R. Clarke, J. Waddington, and J. N. Wallace. The application of Kalman filtering to the load/pressure control of coal-fired boilers. In IEE Colloquium on KAlman Filters: Introduction, Applications and Future Developments, volume 27, pages 2/1--2/6, London, UK, Feburary 1989.
• 15: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 16: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 17: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 18: R. E. Kalman. A new approach to linear filtering and prediction problems. Transactions of the ASME-Journal of Basic Engineering, 82 (Series D):35--45, March 1960.
• 19: I. Lazaridis and S. Mehrotra. Capturing sensor-generated time series with quality guarantess. In Proceedings of the ICDE Intl. Conf. on Data Engineering, pages 429--420, Bangalore, India, March 5--8 2003.
• 20: P. S. Maybeck. Stochastic Models, Estimation, and Control, volume 1. Academic Press, New York, NY, USA, 1979.
• 21: 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 the CIDR Conf. on Innovative Data Systems Research, Asilomar, California, USA, January 2003.
• 22: Basic generation services data room, http://www.bgs-auction.com/bgs.dataroom.asp. Newark, NJ, 2003.
• 23: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 24: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 25: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 26: C. Pereira, S. Gupta, K. Niyogi, I. Lazaridis, S. Mehrotra, and R. Gupta. Energy efficient communication for reliability and quality aware sensor networks. Technical report, University of California at Irvine and University of California at San Diego, April 2003.
• 27: V. Raghunathan, C. Schurgers, S. Park, and M. Srivastava. Energy aware wireless microsensor networks. IEEE Signal Processing Magazine, 19(2):40--50, March 2002.
• 28: Tajana Simunic , Haris Vikalo , Peter Glynn , Giovanni De Micheli, Energy efficient design of portable wireless systems, Proceedings of the 2000 international symposium on Low power electronics and design, p.49-54, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344197]
• 29: G. Strang. Introduction to Applied Mathematics. Wellesley-Cambridge Press, Wellesley, MA, USA, 1986.
• 30: N. Tatbul, U. Cetintemel, S. Zdonik, M. Cherniack, and M. Stonebraker. Load shedding in a data stream manager. In Processdings of VLDB Intl. Conf. on Very Large Data Bases, pages 309--320, Berlin, Germany, September 2003.
• 31: The internet traffic archive, http://ita.ee.lbl.gov. Lawrence Berkeley National Laboratory, USA, April 2000.
• 32: G. Welch and G. Bishop. An introduction to the Kalman filter. In ACM SIGGRAPH Intl. Conf. on Computer Graphics and Interactive Techniques, Los Angeles, CA, USA, August 2001.
• 33: Gang Wu , Yi Wu , Long Jiao , Yuan-Fang Wang , Edward Y. Chang, Multi-camera spatio-temporal fusion and biased sequence-data learning for security surveillance, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957126]
• 34: W. Wu, M. J. Black, E. B. Y. Gao, M. Serruya, A. Shaikhouni, and J. P. Donoghue. Neural decoding of cursor motion using a Kalman filter. In Neural Information Processing Systems: Natural and Synthetic, pages 133--140, Vancouver, British Columbia, Canada, December 2002.
• 35: Y. Yao and J. Gehrke. Query processing for sensor networks. In Proceedings of the CIDR Conf. on Innovative Data Systems Research, Asilomar, CA, USA, January 2003.
• 36: Online Data Mining for Co-Evolving Time Sequences, Proceedings of the 16th International Conference on Data Engineering, p.13, February 28-March 03, 2000