Ankur Jain
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.
- D. Abadiand, D. Carneyand, U. Cetintemel, M. Cherniack, C. Convey, C. Erwin, E. Galvez, M. Hatoun, J. Hwang, A. Maskey, A. Rasin, A. Singer, M. Stonebraker, N. Tatbul, Y. Xing, R. Yan, and S. Zdonik. Aurora: A data stream management system (demonstration). In Proceedings of the ACM SIGMOD Intl. Conf. on Management of Data, San Diego, CA, USA, June 2003. Google Scholar
Digital Library
- 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.Google Scholar
- A. Arasu, B. Babcock, S. Babu, J. McAlister, and J. Widom. Characterizing memory requirements for queries over continuous data streams. In Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 221--232, Madison, WI, USA, June 2002. Google ScholarDigital Library
- 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.Google Scholar
- B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 1--16, Madison, WI, USA, June 2002. Google ScholarDigital Library
- B. Babcock, M. Datar, and R. Motwani. Load shedding for aggregation queries over data streams. In Proceedings of the ICDE Intl. Conf. on Data Engineering, Boston, MA, USA, March 2004. Google ScholarDigital Library
- 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.Google Scholar
- A. Bletsas. Evaluation of Kalman filtering for network time keeping. In Proceedings of PerCom IEEE Intl. Conf. on Pervasive Computing and Communications, pages 289--296, Fort Worth, TX, USA, March 2003. Google ScholarDigital Library
- R. F. Boisvert, B. Miller, R. Pozo, K. Remington, J. Hicklin, C. Moler, and P. Webb. JAMA: A java matrix package.Google Scholar
- R. G. Brown. Introduction to Random Signal Analysis and Kalman Filtering. Wiley, New York, NY, USA, 1983.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Evaluating probabilistic queries over imprecise data. In Proceedings of ACM SIGMOD Intl. Conf. on Management of Data, pages 551--562, San Diego, CA, USA, June 2003. Google ScholarDigital Library
- 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.Google Scholar
- R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification, 2nd Edition. Wiley, New York, NY, USA, 2001. Google ScholarDigital Library
- L. Golab and M. T. Özsu. Issues in data stream management. SIGMOD Record, 32(2):5--14, June 2003. Google ScholarDigital Library
- Z. G. Ives, D. Florescu, M. Friedman, A. Levy, and D. S. Weld. An adaptive query execution system for data integration. In Proc. of ACM SIGMOD Intl. Conf. on Management of Data, pages 299--310, Philadelphia, PA, USA, June 1999. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- P. S. Maybeck. Stochastic Models, Estimation, and Control, volume 1. Academic Press, New York, NY, USA, 1979.Google Scholar
- 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.Google Scholar
- Basic generation services data room, http://www.bgs-auction.com/bgs.dataroom.asp. Newark, NJ, 2003.Google Scholar
- C. Olston, J. Jiang, and J. Widom. Adaptive filters for continuous queries over distributed data streams. In Proceedings of the ACM SIGMOD Intl. Conf. on Management of Data, pages 563--574, San Diego, CA, USA, June 2003. Google ScholarDigital Library
- C. Olston, B. Loo, and J. Widom. Adaptive precision setting for cached approximate values. In Processdings of ACM SIGMOD Intl. Conf. on Management of Data, pages 355--366, Santa Barbara, CA, USA, May 2001. Google ScholarDigital Library
- C. Olston, B. T. Loo, and J. Widom. Adaptive precision setting for cached approximate values. In Proceedings of the ACM SIGMOD Intl. Conf. on Management of Data, pages 355--366, Santa Barbara, CA, USA, May 2001. Google ScholarDigital Library
- 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.Google Scholar
- V. Raghunathan, C. Schurgers, S. Park, and M. Srivastava. Energy aware wireless microsensor networks. IEEE Signal Processing Magazine, 19(2):40--50, March 2002.Google ScholarCross Ref
- T. Simunic, H. Vikalo, P. Glynn, and G. D. Micheli. Energy efficient design of portable wireless systems. In Proceedings of ISLPED IEEE Symposium on Low Power Electronics and Design, pages 49--54, Rapallo, Italy, July 2000. Google ScholarDigital Library
- G. Strang. Introduction to Applied Mathematics. Wellesley-Cambridge Press, Wellesley, MA, USA, 1986.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- The internet traffic archive, http://ita.ee.lbl.gov. Lawrence Berkeley National Laboratory, USA, April 2000.Google Scholar
- 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.Google Scholar
- G. Wu, Y. Wu, L. Jiao, Y.-F. Wang, and E. Y. Chang. Multi-camera spatio-temporal fusion and biased sequence-data learning for security surveillance. In Proceedings of the ACM Intl. Conf. on Multimedia, pages 528--538, Berkeley, CA, USA, 2003. ACM Press. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- B.-K. Yi, N. Sidiropoulos, T. Johnson, H. V. Jagadish, C. Faloutsos, and A. Biliris. Online data mining for co-evolving time sequences. in Proceedings of the ICDE Intl. Conf. on Data Engineering, pages 13--22, San Diego, CA, USA, March 2000. Google ScholarDigital Library
Recommendations
Kalman filter/smoother-based design and implementation of digital IIR filters
Highlights- A Kalman filter framework for finding the optimal response of digital IIR filters is proposed.
AbstractRecently, a unified framework was proposed for forward-backward filtering and penalized least-squares optimization. It was shown that forward-backward filtering can be presented as instances of penalized least-squares optimization. In ...
Accuracy analysis of sigma-point Kalman filters
CCDC'09: Proceedings of the 21st annual international conference on Chinese control and decision conferenceSigma-point Kalman filters are new filters with high precision aimed at nonlinear system. Within the framework of linear minimum variance recursive algorithm, the accuracy of state estimation using the sigma-point Kalman filters mainly depends on the ...
Adaptive median filters: new algorithms and results
Based on two types of image models corrupted by impulse noise, we propose two new algorithms for adaptive median filters. They have variable window size for removal of impulses while preserving sharpness. The first one, called the ranked-order based ...
Comments