A symbolic representation of time series, with implications for streaming algorithms

ABSTRACT

The parallel explosions of interest in streaming data, and data mining of time series have had surprisingly little intersection. This is in spite of the fact that time series data are typically streaming data. The main reason for this apparent paradox is the fact that the vast majority of work on streaming data explicitly assumes that the data is discrete, whereas the vast majority of time series data is real valued.Many researchers have also considered transforming real valued time series into symbolic representations, nothing that such representations would potentially allow researchers to avail of the wealth of data structures and algorithms from the text processing and bioinformatics communities, in addition to allowing formerly "batch-only" problems to be tackled by the streaming community. While many symbolic representations of time series have been introduced over the past decades, they all suffer from three fatal flaws. Firstly, the dimensionality of the symbolic representation is the same as the original data, and virtually all data mining algorithms scale poorly with dimensionality. Secondly, although distance measures can be defined on the symbolic approaches, these distance measures have little correlation with distance measures defined on the original time series. Finally, most of these symbolic approaches require one to have access to all the data, before creating the symbolic representation. This last feature explicitly thwarts efforts to use the representations with streaming algorithms.In this work we introduce a new symbolic representation of time series. Our representation is unique in that it allows dimensionality/numerosity reduction, and it also allows distance measures to be defined on the symbolic approach that lower bound corresponding distance measures defined on the original series. As we shall demonstrate, this latter feature is particularly exciting because it allows one to run certain data mining algorithms on the efficiently manipulated symbolic representation, while producing identical results to the algorithms that operate on the original data. Finally, our representation allows the real valued data to be converted in a streaming fashion, with only an infinitesimal time and space overhead.We will demonstrate the utility of our representation on the classic data mining tasks of clustering, classification, query by content and anomaly detection.

REFERENCES

• 1: Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Zaït, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, September 11-15, 1995
• 2: Henrik André-Jönsson , Dushan Z. Badal, Using Signature Files for Querying Time-Series Data, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.211-220, June 24-27, 1997
• 3: 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]
• 4: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 5: Bastogne, T., Noura, H., Richard A. amp; Hittinger, J. M. (2002). Application of Subspace Methods to the Identification of a Winding Process. In proceedings of the 4th European Control Conference, Vol. 5, Brussels.
• 6: Berndt, D. amp; Clifford, J. (1994) Using Dynamic Time Warping to Find Patterns in Time Series. In proceedings of the Workshop on Knowledge Discovery in Databases, at the 12th Int'l Conference on Artificial Intelligence. July 31-Aug 4, Seattle, WA. pp 229--248.
• 7: Efficient Time Series Matching by Wavelets, Proceedings of the 15th International Conference on Data Engineering, p.126, March 23-26, 1999
• 8: Corinna Cortes , Kathleen Fisher , Daryl Pregibon , Anne Rogers, Hancock: a language for extracting signatures from data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.9-17, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347094]
• 9: Dasgupta, D. amp; Forrest, S. (1996) Novelty Detection in Time Series Data using Ideas from Immunology. In proceedings of The International Conference on Intelligent Systems. June 19--21.
• 10: Mayur Datar , S. Muthukrishnan, Estimating Rarity and Similarity over Data Stream Windows, Proceedings of the 10th Annual European Symposium on Algorithms, p.323-334, September 17-21, 2002
• 11: Daw, C. S., Finney, C. E. A. amp; Tracy, E. R. (2001). Symbolic Analysis of Experimental Data. Review of Scientific Instruments. (2002-07-22).
• 12: Chris Ding , Xiaofeng He , Hongyuan Zha , Horst D. Simon, Adaptive dimension reduction for clustering high dimensional data, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.147, December 09-12, 2002
• 13: Durbin, R., Eddy, S., Krogh, A. amp; Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
• 14: 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
• 15: Fayyad, U., Reina, C. &. Bradley, P. (1998). Initialization of Iterative Refinement Clustering Algorithms. In proceedings of the 4th International Conference on Knowledge Discovery and Data Mining. New York, NY, Aug 27--31. pp 194--198.
• 16: Pierre Geurts, Pattern Extraction for Time Series Classification, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.115-127, September 03-05, 2001
• 17: Aristides Gionis , Heikki Mannila, Finding recurrent sources in sequences, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.123-130, April 10-14, 2003, Berlin, Germany [doi>10.1145/640075.640091]
• 18: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 19: Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263688]
• 20: 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]
• 21: Konstantinos Kalpakis , Dhiral Gada , Vasundhara Puttagunta, Distance Measures for Effective Clustering of ARIMA Time-Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.273-280, November 29-December 02, 2001
• 22: 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
• 23: 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]
• 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: Keogh, E. amp; Pazzani, M. (1998). An Enhanced Representation of Time Series Which Allows Fast and Accurate Classification, Clustering and Relevance Feedback. In proceedings of the 4th Int'l Conference on Knowledge Discovery and Data Mining. New York, NY, Aug 27--31. pp 239--241.
• 26: Lin, J., Keogh, E., Lonardi, S. amp; Patel, P. (2002). Finding Motifs in Time Series. In proceedings of the 2nd Workshop on Temporal Data Mining, at the 8th ACM SIGKDD Int'l Conference on Knowledge Discovery and Data Mining. Edmonton, Alberta, Canada, July 23--26. pp. 53--68.
• 27: Larsen, R. J. amp; Marx, M. L. (1986). An Introduction to Mathematical Statistics and Its Applications. Prentice Hall, Englewood, Cliffs, N.J. 2nd Edition.
• 28: Stefano Lonardi , A. Apostolico, Global detectors of unusual words: design, implementation, and applications to pattern discovery in biosequences, 2001
• 29: Reinert, G., Schbath, S. amp; Waterman, M. S. (2000). Probabilistic and Statistical Properties of Words: An Overview. Journal of Computational. Biology. Vol. 7, pp 1--46.
• 30: John F. Roddick , Kathleen Hornsby , Myra Spiliopoulou, An Updated Bibliography of Temporal, Spatial, and Spatio-temporal Data Mining Research, Proceedings of the First International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining-Revised Papers, p.147-164, September 12, 2000
• 31: 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]
• 32: Staden, R. (1989). Methods for Discovering Novel Motifs in Nucleic Acid Sequences. Computer Applications in Biosciences. Vol. 5(5). pp 293--298.
• 33: Jeremy Buhler , Martin Tompa, Finding motifs using random projections, Proceedings of the fifth annual international conference on Computational biology, p.69-76, April 22-25, 2001, Montreal, Quebec, Canada [doi>10.1145/369133.369172]
• 34: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 35: Byoung-Kee Yi , Christos Faloutsos, Fast Time Sequence Indexing for Arbitrary Lp Norms, Proceedings of the 26th International Conference on Very Large Data Bases, p.385-394, September 10-14, 2000

INDEX TERMS

Keywords:
data mining, data streams, discretize, symbolic, time series