An online spatio-temporal association rule mining framework for analyzing and estimating sensor data

ABSTRACT

A sensor network is a valuable new form of collective computational instrumentation by virtue of its ability to sense physical quantities of interest and to transmit such readings via sub-networks of nodes/computers for processing. Such computing environment typically generates massive amounts of data rapidly in real-time. These infinite volumes of online time-series are formally characterized as data streams. The wealth of fast incoming data streams presents both overhead and logistic challenges for sensor network applications. In this research, we introduce an online data mining framework to serve as an overhead-bounded knowledge discovery tool for sensornet applications. Our framework extends the notions of traditional association rules to multivariate continuous data and uses spatio-temporal correlations to make intelligent inferences about the monitored variables. Our mining framework is additionally pertinent to data estimation, which is an important capability given the inevitability of data loss/corruption with the current sensornet technology. Experimentation shows efficiency of our approach both in terms of overhead cost and quality of missing data estimates.

REFERENCES

• 1: M. Halatchev and L. Gruenwald. "Estimating Missing Values in Related Sensor Data Streams". Proceedings of International Conference on Management of Data, January 2005.
• 2: L. Gruenwald, H. Chok, M. Aboukhamis. "Using Data Mining to Estimate Missing Sensor Data". Proceedings of Seventh IEEE International Conference on Data Mining Workshops. ICDM Workshops 2007, pages 207--212, 2007.
• 3: S. Papadimitriou, J. Sun, C. Faloutsos. "Streaming Pattern Discovery in Multiple Time-Series". Proceedings of the 31st International Conference on VLDB, pages 697--708, 2005.
• 4: C. Giannella, J. Han, J. Pei, X. Yan, and P. Yu. in H. Kargupta, A. Joshi, K. Sivakumar, and Y. Yesha (eds.). "Mining Frequent Patterns in Data Streams at Multiple Time Granularities". Proceedings of the Next Generation Data Mining, AAAI/MIT, 2003.
• 5: X. Chen, I. Petrounias. "An Architecture for Temporal Data Mining". Proceedings of the IEEE Colloquium on Knowledge Discovery and Data Mining, pp. 8/1--8/4. 1998.
• 6: H. Chok. "Spatio-Temporal Association Rule Mining Framework for Estimating Missing Data in Sensor Networks and Analyzing Trend Evolution of Co-evolving Multi-Dimensional Data Streams". Master's Thesis, the University of Oklahoma, 2009.
• 7: NASA/JPL Sensor Webs Project, http://caupanga.huntington.org/swim/.
• 8: R. Aggarwal; T. Imielinski. "A. Swami: Mining Association Rules Between Sets of Items in Large Databases". Proceedings of the 1993 ACM SIGMOD Conference, pages 207--216, 1993.
• 9: R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Manku, C. Olston, J. Rosenstein, R. Varma. "Query Processing, Approximation, and Resource Management in a Data Stream Management System". Proceedings of the Conference on Innovative Data Systems Research (CIDR), pages 245--256, 2003.
• 10: D. Abadi, D. Carney, 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, S. Zdonik. "Aurora: A Data Stream Management System". Proceedings of the 2003 ACM SIGMOD International Conference on Management of data, pages: 666--666, San Diego, CA, 2003.
• 11: S. R. Madden, M. J. Franklin, J. M. Hellerstein, W. hong. Tiny DB: An Acquisitional Query Processing System for Sensor Networks. ACM Transactions on Database Systems, Vol. 30, No. 1, pages: 122--173, 2005.
• 12: W. P. Elderton, N. L. Johnson. "Systems of Frequency Curves". Cambridge University Press, 1969.
• 13: W. M. McKeeman. "Algorithm 145: Adaptive numerical integration by Simpson's rule". Source Communications of the ACM, Vol. 5, page 604, 1962.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Experimentation, Performance

Keywords:
data estimation, knowledge discovery, sensor databases, spatio-temporal data mining