On the brink: searching for drops in sensor data

ABSTRACT

Sensor networks have been widely used to collect data about the environment. When analyzing data from these systems, people tend to ask exploratory questions---they want to find subsets of data, namely signal, reflecting some characteristics of the environment. In this paper, we study the problem of searching for drops in sensor data. Specifically, the search is to find periods in history when a certain amount of drop over a threshold occurs in data within a time span. We propose a framework, SegDiff, for extracting features, compressing them, and transforming the search into standard database queries. Approximate results are returned from the framework with the guarantee that no true events are missed and false positives are within a user specified tolerance. The framework efficiently utilizes space and provides fast response to users' search. Experimental results with real world data demonstrate the efficiency of our framework with respect to feature size and search time.

REFERENCES

• 1: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 2: Harry Hochheiser , Ben Shneiderman, Dynamic query tools for time series data sets: timebox widgets for interactive exploration, Information Visualization, v.3 n.1, p.1-18, Spring 2004 [doi>10.1145/993176.993177]
• 3: Eamonn Keogh, A decade of progress in indexing and mining large time series databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 5: Eamonn J. Keogh , Selina Chu , David Hart , Michael J. Pazzani, An Online Algorithm for Segmenting Time Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.289-296, November 29-December 02, 2001
• 6: E. Keogh and M. J. Pazzani. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In Proc. of KDD, pages 239--243, 1998.
• 7: Q. Li, I. F. V. Lopez, and B. Moon. Skyline index for time series data. IEEE Transactions on Knowledge and Data Engineering (TKDE), 16(6):669--684, 2004.
• 8: Junshui Ma , Simon Perkins, Online novelty detection on temporal sequences, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956828]
• 9: Yunyao Qu , Changzhou Wang , X. Sean Wang, Supporting fast search in time series for movement patterns in multiple scales, Proceedings of the seventh international conference on Information and knowledge management, p.251-258, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288664]
• 10: L. Reznik, G. V. Pless, and T. A. Karim. Signal change detection in sensor networks with artificial neural network structure. In Proc. of IEEE CIHSPS, pages 44--51, 2005.
• 11: M. Sharifzadeh, F. Azmoodeh, and C. Shahabi. Change detection in time series data using wavelet footprints. In Proc. of SSTD, pages 127--144, 2005.
• 12: Hagit Shatkay , Stanley B. Zdonik, Approximate Queries and Representations for Large Data Sequences, Proceedings of the Twelfth International Conference on Data Engineering, p.536-545, February 26-March 01, 1996
• 13: Changzhou Wang , Xiaoyang Sean Wang, Supporting Content-Based Searches on Time Series via Approximation, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.69, July 26-28, 2000 [doi>10.1109/SSDM.2000.869779]
• 14: Huanmei Wu , Betty Salzberg , Donghui Zhang, Online event-driven subsequence matching over financial data streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007574]
• 15: Yunyue Zhu , Dennis Shasha, Efficient elastic burst detection in data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956789]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems