Visually mining and monitoring massive time series

ABSTRACT

Moments before the launch of every space vehicle, engineering discipline specialists must make a critical go/no-go decision. The cost of a false positive, allowing a launch in spite of a fault, or a false negative, stopping a potentially successful launch, can be measured in the tens of millions of dollars, not including the cost in morale and other more intangible detriments. The Aerospace Corporation is responsible for providing engineering assessments critical to the go/no-go decision for every Department of Defense space vehicle. These assessments are made by constantly monitoring streaming telemetry data in the hours before launch. We will introduce VizTree, a novel time-series visualization tool to aid the Aerospace analysts who must make these engineering assessments. VizTree was developed at the University of California, Riverside and is unique in that the same tool is used for mining archival data and monitoring incoming live telemetry. The use of a single tool for both aspects of the task allows a natural and intuitive transfer of mined knowledge to the monitoring task. Our visualization approach works by transforming the time series into a symbolic representation, and encoding the data in a modified suffix tree in which the frequency and other properties of patterns are mapped onto colors and other visual properties. We demonstrate the utility of our system by comparing it with state-of-the-art batch algorithms on several real and synthetic datasets.

REFERENCES

• 1: Charu C. Aggarwal, Towards effective and interpretable data mining by visual interaction, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507518]
• 2: 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]
• 3: Juan P. Caraça-Valente , Ignacio López-Chavarrías, Discovering similar patterns in time series, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.497-505, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347192]
• 4: Cardle, M. (2004). Ph.D Thesis, in progress. University of Cambridge.
• 5: Chen Li , Edward Chang , Hector Garcia-Molina , Gio Wiederhold, Clustering for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.792-808, July 2002 [doi>10.1109/TKDE.2002.1019214]
• 6: Chen, L., Ozsu, T. & Oria, V. (2003). Symbolic Representation and Retrieval of Moving Object Trajectories. University of Waterloo. 2003.
• 7: Bill Chiu , Eamonn Keogh , Stefano Lonardi, Probabilistic discovery of time series motifs, 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.956808]
• 8: Crochemore, M., Czumaj, A., Gasjeniec, L., Jarominek, S., Lecroq, T., Plandowski, W. & Rytter, W. (1994). Speeding Up Two String-Matching Algorithms. Algorithmica. vol. 12(4/5). pp. 247-267.
• 9: Dasgupta, D. & Forrest, S. (1999). Novelty Detection in Time Series Data Using Ideas from Immunology. In proceedings of the 8th Int'l Conference on Intelligent Systems. Denver, CO, Jun 24-26.
• 10: Durbin, R., Eddy, S., Krogh, A. & Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
• 11: 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
• 12: Gabglio, A. (1888). Theoria Generale Della Statistica, 2nd ed. Milan.
• 13: Goldberger, A. L., Amaral, L. A., Glass, L., Hausdorff, J. M., Ivanov, P. C., Mark, R. G., Mietus, J. E., Moody, G. B., Peng, C. K. & Stanley, H. E. (2000). PhysioBank, PhysioToolkit, and PhysioNet: Componenets of a New Research Resource for Complex Physiologic Signals. Circulation. vol. 101(23), June 13. pp. e215--e220. {Circulation Electronic Pages; http://circ.ahajournals.org/cgi/content/full/101/23/e215}
• 14: Harry Hochheiser , Ben Shneiderman, Interactive Exploration of Time Series Data, Proceedings of the 4th International Conference on Discovery Science, p.441-446, November 25-28, 2001
• 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: Huettel, S., Mack, P. B. & McCarthy, G. (2002). Perceiving Patterns in Random Series: Dynamic Processing of Sequence in Prefrontal Cortex. Nature Neuroscience. vol. 5. pp. 485--490.
• 17: Isaac, D. & Lynnes, C. (2003). Automated Data Quality Assessment in the Intelligent Archive, White Paper prepared for the Intelligent Data Understanding program. 2003. pp. 17.
• 18: Xiaoming Jin , Likun Wang , Yuchang Lu , Chunyi Shi, Indexing and Mining of the Local Patterns in Sequence Database, Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning, p.68-73, August 12-14, 2002
• 19: Daniel A. Keim, Information Visualization and Visual Data Mining, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.1-8, January 2002 [doi>10.1109/2945.981847]
• 20: Keogh, E. The UCR Time Series Data Mining Archive. http://www.cs.ucr.edu/~eamonn/tsdma/index.html
• 21: 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
• 22: Eamonn Keogh , Shruti Kasetty, On the need for time series data mining benchmarks: a survey and empirical demonstration, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775062]
• 23: Keogh, E. & Lin, J. (2004). Clustering of Time Series Subsequences is Meaningless: Implications for Previous and Future Research. Knowledge and Information Systems Journal. To Appear
• 24: Eamonn Keogh , Stefano Lonardi , Bill 'Yuan-chi' Chiu, Finding surprising patterns in a time series database in linear time and space, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775128]
• 25: Kim, S., Kim, Y., Ahn, T., Nam, H. K., Han, B. J. & Kim, S. M. (2000). Visualysis: A Tool for Biological Sequence Analysis. In proceedings of the 4th Int'l Conference on Computational Molecular Biology. Tokyo, Japan, Apr 8--11.
• 26: Lankford, J. P. & Quan, A. (2002). Evolution of Knowledge-Based Applications for Launch Support. In proceedings of Ground System Architecture Workshop. El Segundo, CA.
• 27: Lin, J. VizTree Website. http://www.cs.ucr.edu/~jessica/viztree.htm
• 28: Jessica Lin , Eamonn Keogh , Stefano Lonardi , Bill Chiu, A symbolic representation of time series, with implications for streaming algorithms, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882086]
• 29: Lin, J., Keogh, E., Patel, P. & Lonardi, S. (2002). Finding Motifs in Time Series. In the 2nd Workshop on Temporal Data Mining, the 8th ACM Int'l Conference on Knowledge Discovery and Data Mining. Edmonton, Alberta, Canada. July 23-26, 2002.
• 30: 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]
• 31: Tim Oates, Identifying distinctive subsequences in multivariate time series by clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.322-326, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312268]
• 32: Tim Oates , Matthew D. Schmill , Paul R. Cohen, A Method for Clustering the Experiences of a Mobile Robot that Accords with Human Judgments, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.846-851, July 30-August 03, 2000
• 33: Ohsaki, M., Sato, Y., Yokoi, H. & Yamaguchi, T. (2003). A Rule Discovery Support System for Sequential Medical Data, in the Case Study of a Chronic Hepatitis Dataset. In Discovery Challenge Workshop, the 14th European Conference on Machine Learning/the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases. Cavtat-Dubrovnik, Croatia. Sep 22-26, 2003.
• 34: 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
• 35: Reinert, G., Schbath, S. & Waterman, M. S. (2000). Probabilistic and Statistical Properties of Words: An Overview. Journal of Computational Biology. vol. 7. pp. 1--46.
• 36: 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]
• 37: Ben Shneiderman, The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations, Proceedings of the 1996 IEEE Symposium on Visual Languages, p.336, September 03-06, 1996
• 38: Tanaka, Y. & Uehara, K. (2003). Discover Motifs in Multi Dimensional Time-Series Using the Principal Component Analysis and the MDL Principle. In proceedings of the 3rd Int'l Conference on Machine Learning and Data Mining in Pattern Recognition. Leipzig, Germany, Jul 5-7. pp. 252--265.
• 39: Edward R. Tufte, The visual display of quantitative information, Graphics Press, Cheshire, CT, 1986
• 40: 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
• 41: Marc Weber , Marc Alexa , Wolfgang Müller, Visualizing Time-Series on Spirals, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.7, October 22-23, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining; Scientific databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Query formulation

General Terms:
Algorithms, Design, Experimentation, Human Factors

Keywords:
anomaly detection, motif discovery, pattern discovery, time series, visualization