A query processor for prediction-based monitoring of data streams

ABSTRACT

Networks of sensors are used in many different fields, from industrial applications to surveillance applications. A common feature of these applications is the necessity of a monitoring infrastructure that analyzes a large number of data streams and outputs values that satisfy certain constraints.

In this paper, we present a query processor for monitoring queries in a network of sensors with prediction functions. Sensors communicate their values according to a threshold policy, and the proposed query processor leverages prediction functions to compare tuples efficiently and to generate answers even in the absence of new incoming tuples. Two types of constraints are managed by the query processor: window-join constraints and value constraints. Uncertainty issues are considered to assign probabilistic values to the results returned to the user. Moreover, we have developed an appropriate buffer management strategy, that takes into account the contributions of the prediction functions contained in the tuples. We also present some experimental results that show the benefits of the proposal.

REFERENCES

• 1: Y. Ahmad, O. Papaemmanouil, U. Cetintemel, and J. Rogers. Simultaneous equation systems for query processing on continuous-time data streams. In 24th International Conference on Data Engineering, ICDE'08, pages 666--675, Washington, 2008. IEEE Computer Society.
• 2: Arvind Arasu , Shivnath Babu , Jennifer Widom, The CQL continuous query language: semantic foundations and query execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.121-142, June 2006 [doi>10.1007/s00778-004-0147-z]
• 3: 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]
• 4: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 6: Paolo Capitani , Paolo Ciaccia, Warping the time on data streams, Data & Knowledge Engineering, v.62 n.3, p.438-458, September, 2007 [doi>10.1016/j.datak.2006.08.012]
• 7: Ying Chen , Fangyan Rao , Xiulan Yu , Dong Liu, CAMEL: A Moving Object Database Approach for Intelligent Location Aware Services, Proceedings of the 4th International Conference on Mobile Data Management, p.331-334, January 21-24, 2003
• 8: Ying Chen , Fangyan Rao , Xiulan YU , Dong Liu , Long Zhang, Managing Location Stream Using Moving Object Database, Proceedings of the 14th International Workshop on Database and Expert Systems Applications, p.916, September 01-05, 2003
• 9: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluation of probabilistic queries over imprecise data in constantly-evolving environments, Information Systems, v.32 n.1, p.104-130, March, 2007 [doi>10.1016/j.is.2005.06.002]
• 10: David Chu , Amol Deshpande , Joseph M. Hellerstein , Wei Hong, Approximate Data Collection in Sensor Networks using Probabilistic Models, Proceedings of the 22nd International Conference on Data Engineering, p.48, April 03-07, 2006 [doi>10.1109/ICDE.2006.21]
• 11: A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Model-based approximate querying in sensor networks. VLDB Journal, 14(4):417--443, 2005.
• 12: Thanaa M. Ghanem, Supporting Predicate-Window Queries in Data Stream Management Systems, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.139, April 03-07, 2006 [doi>10.1109/ICDEW.2006.140]
• 13: Thanaa M. Ghanem , Walid G. Aref , Ahmed K. Elmagarmid, Exploiting predicate-window semantics over data streams, ACM SIGMOD Record, v.35 n.1, p.3-8, March 2006 [doi>10.1145/1121995.1121996]
• 14: Samir Goel , Tomasz Imielinski, Prediction-based monitoring in sensor networks: taking lessons from MPEG, ACM SIGCOMM Computer Communication Review, v.31 n.5, October 2001 [doi>10.1145/1037107.1037117]
• 15: J. D. Gooijer and R. Hyndman. 25 years of IIF time series forecasting: a selective review. Department of Econometrics and Business Statistics, Monash University, 2005.
• 16: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 17: Moustafa A. Hammad , Walid G. Aref , Ahmed K. Elmagarmid, Stream window join: tracking moving objects in sensor-network databases, Proceedings of the 15th International Conference on Scientific and Statistical Database Management, p.75-84, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214967]
• 18: Sergio Ilarri , Ouri Wolfson , Eduardo Mena , Arantza Illarramendi , Naphtali Rishe, Processing of Data Streams with Prediction Functions, Proceedings of the 39th Annual Hawaii International Conference on System Sciences, p.237.1, January 04-07, 2006 [doi>10.1109/HICSS.2006.393]
• 19: S. Ilarri, O. Wolfson, E. Mena, A. Illarramendi, and P. Sistla. An architecture for prediction-based monitoring of data streams. Technical Report RR-08-08, University of Zaragoza, September 2008.
• 20: Ankur Jain , Edward Y. Chang, Adaptive sampling for sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052202]
• 21: Ankur Jain , Edward Y. Chang , Yuan-Fang Wang, Adaptive stream resource management using Kalman Filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007573]
• 22: Christine E. Jones , Krishna M. Sivalingam , Prathima Agrawal , Jyh Cheng Chen, A Survey of Energy Efficient Network Protocols for Wireless Networks, Wireless Networks, v.7 n.4, p.343-358, 08/01/2001 [doi>10.1023/A:1016627727877]
• 23: K. Kowalski and W.-H. Steeb. Nonlinear Dynamical Systems and Carleman Linearization. World Scientific, Singapore, 1991.
• 24: Vibhore Kumar , Brian F. Cooper , Shamkant B. Navathe, Predictive filtering: a learning-based approach to data stream filtering, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052203]
• 25: D. Lin, B. Cui, and D. Yang. Optimizing moving queries over moving object data streams. In 12th International Conference on Database Systems for Advanced Applications, DAASFA'07, volume 4443 of Lecture Notes in Computer Science, pages 563--575, Berlin, 2007. Springer.
• 26: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 27: J. Miles and M. Shevlin. Applying Regression and Correlation: A Guide for Students and Researchers. SAGE Publications, London, 2001.
• 28: J. Myllymaki and J. Kaufman. IBM Location Transponder. IBM alphaworks, http://www.alphaworks.ibm.com/tech/transponder, 2002.
• 29: A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , K. Chrysanthis, Balancing energy efficiency and quality of aggregate data in sensor networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.384-403, December 2004 [doi>10.1007/s00778-004-0138-0]
• 30: Adam Silberstein , Rebecca Braynard , Jun Yang, Constraint chaining: on energy-efficient continuous monitoring in sensor networks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142492]
• 31: A. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Querying the uncertain position of moving objects. In Temporal Databases: Research and Practice, volume 1399 of Lecture Notes in Computer Science, pages 310--337, Berlin, 1998. Springer.
• 32: Yufei Tao , Dimitris Papadias, Time-parameterized queries in spatio-temporal databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564730]
• 33: Kristian Torp , Christian S. Jensen , Richard Thomas Snodgrass, Effective timestamping in databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.267-288, February 2000 [doi>10.1007/s007780050008]
• 34: Ouri Wolfson , Sam Chamberlain , Son Dao , Liqin Jiang , Gisela Mendez, Cost and Imprecision in Modeling the Position of Moving Objects, Proceedings of the Fourteenth International Conference on Data Engineering, p.588-596, February 23-27, 1998
• 35: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752]