Optimal multi-scale patterns in time series streams

ABSTRACT

We introduce a method to discover optimal local patterns, which concisely describe the main trends in a time series. Our approach examines the time series at multiple time scales (i.e., window sizes) and efficiently discovers the key patterns in each. We also introduce a criterion to select the best window sizes, which most concisely capture the key oscillatory as well as aperiodic trends. Our key insight lies in learning an optimal orthonormal transform from the data itself, as opposed to using a predetermined basis or approximating function (such as piecewise constant, short-window Fourier or wavelets), which essentially restricts us to a particular family of trends. We go one step further, lifting even that limitation. Furthermore, our method lends itself to fast, incremental estimation in a streaming setting. Experimental evaluation shows that our method can capture meaningful patterns in a variety of settings. Our streaming approach requires order of magnitude less time and space, while still producing concise and informative patterns.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: [2] E. Bingham, A. Gionis, N. Haiminen, H. Hiisilä, H. Mannila, and E. Terzi. Segmentation and dimensionality reduction. In SDM, 2006.
• 3: [3] M. Brand. Fast online SVD revisions for lightweight recommender systems. In SDM, 2003.
• 4: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 5: [5] Y. Chen, G. Dong, J. Han, B. W. Wah, and J. Wang. Multi-dimensional regression analysis of time-series data streams. In VLDB, 2002.
• 6: 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]
• 7: [7] G. Das, K.-I. Lin, H. Mannila, G. Renganathan, and P. Smyth. Rule discovery from time series. In KDD, 1998.
• 8: Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Compressing historical information in sensor networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007628]
• 9: [9] M. G. Elefky, W. G. Aref, and A. K. Elmagarmid. Using convolution to mine obscure periodic patterns in one pass. In EDBT, 2004.
• 10: [10] M. G. Elefky, W. G. Aref, and A. K. Elmagarmid. WARP: Time warping for periodicity detection. In ICDM, 2005.
• 11: 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
• 12: [12] M. Ghil, M. Allen, M. Dettinger, K. Ide, D. Kondrashov, M. Mann, A. Robertson, A. Saunders, Y. Tian, F. Varadi, and P. Yiou. Advanced spectral methods for climatic time series. Rev. Geophys., 40(1), 2002.
• 13: Sudipto Guha , D. Gunopulos , Nick Koudas, Correlating synchronous and asynchronous 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.956814]
• 14: Ming-Jyh Hsieh , Ming-Syan Chen , Philip S. Yu, Integrating DCT and DWT for approximating cube streams, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099588]
• 15: [15] A. Hyvärinen, P. Hoyer, and E. Oja. Sparse code shrinkage for image denoising. In WCCI, 1998.
• 16: [16] T. Idé and K. Inoue. Knowledge discovery from heterogeneous dynamic systems using change-point correlations. In SDM, 2005.
• 17: Piotr Indyk , Nick Koudas , S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Proceedings of the 26th International Conference on Very Large Data Bases, p.363-372, September 10-14, 2000
• 18: [18] I. T. Jolliffe. Principal Component Analysis. Springer, 2nd edition, 2002.
• 19: [19] J. Lin, M. Vlachos, E. J. Keogh, and D. Gunopulos. Iterative incremental clustering of time series. In EDBT, 2004.
• 20: Song Lin , Dimitrios Gunopulos , Vana Kalogeraki , Stefano Lonardi, A Data Compression Technique for Sensor Networks with Dynamic Bandwidth Allocation, Proceedings of the 12th International Symposium on Temporal Representation and Reasoning (TIME'05), p.186-188, June 23-25, 2005 [doi>10.1109/TIME.2005.6]
• 21: Vasileios Megalooikonomou , Qiang Wang , Guo Li , Christos Faloutsos, A Multiresolution Symbolic Representation of Time Series, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.668-679, April 05-08, 2005 [doi>10.1109/ICDE.2005.10]
• 22: [22] D. D. Muresan and T. W. Parks. Adaptive principal components and image denoising. In ICIP, 2003.
• 23: Themistoklis Palpanas , Michail Vlachos , Eamonn Keogh , Dimitrios Gunopulos , Wagner Truppel, Online Amnesic Approximation of Streaming Time Series, Proceedings of the 20th International Conference on Data Engineering, p.338, March 30-April 02, 2004
• 24: Spiros Papadimitriou , Anthony Brockwell , Christos Faloutsos, Adaptive, unsupervised stream mining, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.222-239, September 2004 [doi>10.1007/s00778-004-0130-8]
• 25: Spiros Papadimitriou , Jimeng Sun , Christos Faloutsos, Streaming pattern discovery in multiple time-series, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 26: Pranav Patel , Eamonn Keogh , Jessica Lin , Stefano Lonardi, Mining Motifs in Massive Time Series Databases, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.370, December 09-12, 2002
• 27: [27] D. B. Percival and A. T. Walden. Wavelet Methods for Time Series Analysis. Cambridge Univ. Press, 2000.
• 28: [28] M. R. Portnoff. Short-time Fourier analysis of sampled speech. IEEE Trans. ASSP, 29(3), 1981.
• 29: [29] G. Strang. Linear Algebra and Its Applications. Brooks Cole, 3rd edition, 1998.
• 30: [30] W. Sweldens and P. Schröder. Building your own wavelets at home. In Wavelets in Computer Graphics, pages 15-87. SIGGRAPH Course notes, 1996.
• 31: [31] M. E. Tipping and C.M. Bishop. Probabilistic principal component analysis. J. Royal Stat. Soc. B, 61(3), 1999.
• 32: [32] J. Villasenor, B. Belzer, and J. Liao. Wavelet filter evaluation for image compression. IEEE Trans. Im. Proc., 4(8), 1995.
• 33: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 34: [34] B. Yang. Projection approximation subspace tracking. IEEE Trans. Sig. Proc., 43(1), 1995.
• 35: Pascal Yiou , Didier Sornette , Michael Ghil, Data-adaptive wavelets and multi-scale singular-spectrum analysis, Physica D, v.142 n.3-4, p.254-290, Aug. 15, 2000 [doi>10.1016/S0167-2789(00)00045-2]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.0 General

General Terms:
Algorithms

Keywords:
SVD, empirical orthogonal functions, local patterns, multi-scale, singular spectrum, stream