Finding surprising patterns in a time series database in linear time and space

ABSTRACT

The problem of finding a specified pattern in a time series database (i.e. query by content) has received much attention and is now a relatively mature field. In contrast, the important problem of enumerating all surprising or interesting patterns has received far less attention. This problem requires a meaningful definition of "surprise", and an efficient search technique. All previous attempts at finding surprising patterns in time series use a very limited notion of surprise, and/or do not scale to massive datasets. To overcome these limitations we introduce a novel technique that defines a pattern surprising if the frequency of its occurrence differs substantially from that expected by chance, given some previously seen data.

REFERENCES

• 1: Alberto Apostolico , Mary Ellen Bock , Stefano Lonardi, Monotony of surprise and large-scale quest for unusual words, Proceedings of the sixth annual international conference on Computational biology, p.22-31, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565200]
• 2: A. Apostolico, M. E. Bock, S. Lonardi, and X. Xu. Efficient detection of unusual words. J. Comput. Bio., 7(1/2):71--94, Jan. 2000.
• 3: Hendrik Blockeel , Johannes Fürnkranz , Alexia Prskawetz , Francesco Billari, Detecting Temporal Change in Event Sequences: An Application to Demographic Data, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.29-41, September 03-05, 2001
• 4: Soumen Chakrabarti , Sunita Sarawagi , Byron Dom, Mining Surprising Patterns Using Temporal Description Length, Proceedings of the 24rd International Conference on Very Large Data Bases, p.606-617, August 24-27, 1998
• 5: G. Das, K.-I. Lin, H. Mannila, G. Renganathan, and P. Smyth. Rule discovery from time series. In Proc. the 4th International Conference of Knowledge Discovery and Data Mining, pages 16--22. AAAI Press, 1998.
• 6: D. Dasgupta and S. Forrest. Novelty detection in time series data using ideas from immunology. In Proc. of The International Conference on Intelligent Systems, 1999.
• 7: C. S. Daw, C. E. A. Finney, and E. R. Tracy. Symbolic analysis of experimental data. Review of Scientific Instruments 2001, Oct. 30--31 2001.
• 8: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, ACM SIGMOD Record, v.23 n.2, p.419-429, June 1994
• 9: M. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.137, October 19-22, 1997
• 10: Tom Fawcett , Foster Provost, Activity monitoring: noticing interesting changes in behavior, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.53-62, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312195]
• 11: W. Feller. An introduction to Probability Theory and its Applications. Wiley, New York, 1968.
• 12: Xianping Ge , Padhraic Smyth, Deformable Markov model templates for time-series pattern matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.81-90, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347109]
• 13: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 14: D. M. Hawkins. Identification of Outliers, Monographs on Applied Probability & Statistics. Chapman and Hall, London, 1980.
• 15: Yun-Wu Huang , Philip S. Yu, Adaptive query processing for time-series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.282-286, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.318357]
• 16: H. V. Jagadish , Nick Koudas , S. Muthukrishnan, Mining Deviants in a Time Series Database, Proceedings of the 25th International Conference on Very Large Data Bases, p.102-113, September 07-10, 1999
• 17: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, ACM SIGMOD Record, v.30 n.2, p.151-162, June 2001
• 18: E. Keogh and M. Pazzani. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In Proc. 4th International Conference on Knowledge Discovery and Data Mining, pages 239--241, 1998.
• 19: Evangelos Kotsakis , Antoni Wolski, MAPS: A Method for Identifying and Predicting Aberrant Behavior in Time Series, Proceedings of the 14th International conference on Industrial and engineering applications of artificial intelligence and expert systems: engineering of intelligent systems, p.314-325, June 04-07, 2001
• 20: Stefano Lonardi , A. Apostolico, Global detectors of unusual words: design, implementation, and applications to pattern discovery in biosequences, 2001
• 21: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 22: Chihcheng Hsu, Efficient Searches for Similar Subsequences of Different Lengths in Sequence Databases, Proceedings of the 16th International Conference on Data Engineering, p.23, February 28-March 03, 2000
• 23: G. Reinert, S. Schbath, and M. S. Waterman. Probabilistic and statistical properties of words: An overview. J. Comput. Bio., 7:1--46, 2000.
• 24: Cyrus Shahabi , Xiaoming Tian , Wugang Zhao, TSA-Tree: A Wavelet-Based Approach to Improve the Efficiency of Multi-Level Surprise and Trend Queries on Time-Series Data, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.55, July 26-28, 2000 [doi>10.1109/SSDM.2000.869778]
• 25: E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249--260, 1995.
• 26: Jarke J. Van Wijk , Edward R. Van Selow, Cluster and Calendar Based Visualization of Time Series Data, Proceedings of the 1999 IEEE Symposium on Information Visualization, p.4, October 24-29, 1999
• 27: P. Weiner. Linear pattern matching algorithm. In Proc. 14th Annual IEEE Symposium on Switching and Automata Theory, pages 1--11, Washington, DC, 1973.
• 28: B. Whitehead and W. A. Hoyt. A function approximation approach to anomaly detection in propulsion system test data. In Proc. AIAA/SAE/ASME/ASEE 29th Joint Propulsion Conference, Monterey, CA, June 1993.
• 29: T. Yairi, Y. Kato, and K. Hori. Fault detection by mining association rules from house-keeping data. In Proc. of International Symposium on Artificial Intelligence, Robotics and Automation in Space, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Keywords:
Markov Model, anomaly detection, feature extraction, novelty detection, suffix tree, time series