Declarative temporal data models for sensor-driven query processing

ABSTRACT

Many sensor network applications monitor continuous phenomena by sampling, and fit time-varying models that capture the phenomena's behaviors. We introduce Pulse, a framework for processing continuous queries over these continuous-time data models. Pulse allows users to declaratively specify both their queries and models, and transforms these queries into simultaneous equation systems, which in many cases are significantly cheaper to process than a stream of discrete tuples. Pulse is able to guarantee user-defined error bounds between query results from continuous-time data models and sampled data, including cases of null results. We present a high-level overview of the design and architecture of Pulse and propose several query optimization techniques that are novel to our context, such as the simplification of our equation systems. We also discuss our plans for extending Pulse to support several novel model types, including differential equations and time series, and outline an abstraction to support query processing on these classes of models.

REFERENCES

• 1: D. Abadi et. al. The design of the Borealis stream processing engine. In CIDR, 2005.
• 2: Amol Deshpande , Samuel Madden, MauveDB: supporting model-based user views in database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142483]
• 3: L. Girod et. al. The case for a signal-oriented data stream management system. In CIDR, 2007.
• 4: Global Disaster Alert and Coordination System (GDACS). http://www.gdacs.org/.
• 5: S. Grumbach, P. Rigaux, M. Scholl, and L. Segoufin. The DEDALE prototype. In Constraint Databases, 2000.
• 6: Marios Hadjieleftheriou , George Kollios , Petko Bakalov , Vassilis J. Tsotras, Complex spatio-temporal pattern queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: Alan C. Hindmarsh , Peter N. Brown , Keith E. Grant , Steven L. Lee , Radu Serban , Dan E. Shumaker , Carol S. Woodward, SUNDIALS: Suite of nonlinear and differential/algebraic equation solvers, ACM Transactions on Mathematical Software (TOMS), v.31 n.3, p.363-396, September 2005 [doi>10.1145/1089014.1089020]
• 8: 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]
• 9: Shawn R. Jeffery , Minos Garofalakis , Michael J. Franklin, Adaptive cleaning for RFID data streams, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 10: Arunprasad P. Marathe , Kenneth Salem, A Language for Manipulating Arrays, Proceedings of the 23rd International Conference on Very Large Data Bases, p.46-55, August 25-29, 1997
• 11: Praveen Seshadri, Enhanced abstract data types in object-relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.130-140, August 1998 [doi>10.1007/s007780050059]
• 12: D. Srivastava. Subsumption and indexing in constraint query languages with linear arithmetic constraints. Ann. Math. Artif. Intell, 8(3--4), 1993.
• 13: Richard H. Wolniewicz , Goetz Graefe, Algebraic Optimization of Computations over Scientific Databases, Proceedings of the 19th International Conference on Very Large Data Bases, p.13-24, August 24-27, 1993
• 14: Yunyue Zhu , Dennis Shasha, Warping indexes with envelope transforms for query by humming, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872780]