Efficient and robust feature extraction and pattern matching of time series by a lattice structure

ABSTRACT

The efficiency of searching scaling-invariant and shifting-invariant shapes in a set of massive time series data can be improved if searching is performed on an approximated sequence which involves less data but contains all the significant features. However, commonly used smoothing techniques, such as moving averages and best-fitting polylines, usually miss important peaks and troughs and deform the time series. In addition, these techniques are not robust, as they often requires users to supply a set of smoothing parameters which has direct effect on the resultant approximation pattern. To address these problems, an algorithm to construct a lattice structure as an underlying framework for pattern matching is proposed in this paper. As inputs, the algorithm takes a time series and users' requirements of level of detail. The algorithm then identifies all the important peaks and troughs (known as controlm points) in the time series and classifies the points into appropriate layers of the lattice structure. The control points in each layer of the structure form an approximation pattern an yet preserve the overall shape of the original series with approximation error lies within certain bound. The lower the layer, the more precise the approximation pattern is. Putting in another way, the algorithm takes different levels of data smoothing into account. Also, the lattice structure can be indexed to further improve the performance of pattern matching.

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: K. P. Chan and W. C. Fu. Efficient time series matching by wavelets. In International Conference on Data Engineering, 1999.
• 3: K. W. Chu, S. K. Lam, and M. H. Wong. An efficient hash-based algorithm for sequence data searching. The Computer Journal, pages 402415, 1998.
• 4: Kelvin Kam Wing Chu , Man Hon Wong, Fast time-series searching with scaling and shifting, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.237-248, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304000]
• 5: 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
• 6: E. Keogh. A fast and robust method for pattern matching in time series database. In In PTOC. of 9th International Conference on Tools with Artificial Intelligence, 1997.
• 7: E. Keogh and P. Smyth. A probabilistic approach to fast pattern matching in time series databases. In In Proc. of the 3rd international conference of Kowledge Discovery and Data Mining, pages 24-30, 1997.
• 8: Eamonn J. Keogh , Michael J. Pazzani, An Indexing Scheme for Fast Similarity Search in Large Time Series Databases, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.56, July 28-30, 1999 [doi>10.1109/SSDM.1999.787621]
• 9: Eamonn J. Keogh , Michael J. Pazzani, Relevance feedback retrieval of time series data, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.183-190, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312676]
• 10: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 11: Sze Kin Lam , Man Hon Wong, A fast projection algorithm for sequence data searching, Data & Knowledge Engineering, v.28 n.3, p.321-339, Dec. 15, 1998 [doi>10.1016/S0169-023X(98)00023-8]
• 12: S. Park, W. W. Chu, J. Yoon, and C. Hsu. Efficient search for similar subsequences of different lengths. In Proc. of the 15th International Conference on Data Engneering, March 2000.
• 13: Pavlidis, T., Horowitz, and S. Segmentation of plane curves. In IEEE 'Pransactions on Computers Vol. C-23 No 8, August 1974.
• 14: C. S. Perng, H. Wang, S. R. Zhang, and D. Parker. Landmarks: A new model for similarity-based pattern querying in time series databases. In Proc. of the 15th International Conference on Data Engineeting, March 2000.
• 15: J. Schwager. Schwager on Futures, Technical Analysis. John Wiley & Sons, 1998.
• 16: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 17: 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]
• 18: Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos, Efficient Retrieval of Similar Time Sequences Under Time Warping, Proceedings of the Fourteenth International Conference on Data Engineering, p.201-208, February 23-27, 1998

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Smoothing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

General Terms:
Algorithms, Performance, Theory