A dimensionality reduction technique for efficient similarity analysis of time series databases

ABSTRACT

Efficiently searching for similarities among time series and discovering interesting patterns is an important and non-trivial problem with applications in many domains. The high dimensionality of the data makes the analysis very challenging. To solve this problem, many dimensionality reduction methods have been proposed. PCA (Piecewise Constant Approximation) and its variant have been shown efficient in time series indexing and similarity retrieval. However, in certain applications, too many false alarms introduced by the approximation may reduce the overall performance dramatically. In this paper, we introduce a new piecewise dimensionality reduction technique that is based on Vector Quantization. The new technique, PVQA (Piecewise Vector Quantized Approximation), partitions each sequence into equi-length segments and uses vector quantization to represent each segment by the closest (based on a distance metric) codeword from a codebook of key-sequences. The efficiency of calculations is improved due to the significantly lower dimensionality of the new representation. We demonstrate the utility and efficiency of the proposed technique on real and simulated datasets. By exploiting prior knowledge about the data, the proposed technique generally outperforms PCA and its variants in similarity searches.

REFERENCES

• 1: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 2: Keogh, E., Chakrabarti, K., Pazzani, M. & Mehrotra, S. (2000). "Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases", Knowledge and Information Systems 3(3): 263--286.
• 3: Lin, J., Keogh, E., Patel, P. & Lonardi, S. (2002). "Finding motifs in time series", 2nd Workshop on Temporal Data Mining at the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. July 23-26. Edmonton, Alberta, Canada.
• 4: Lloyd, S. P. (1982). "Least squares quantization in PCM", IEEE Transactions on Information Theory, IT(28), pp. 127--135.
• 5: Stanford Genomic Resources. http://genome-www.stanford.edu/nci60
• 6: UCI KDD Archive. http://kdd.ics.uci.edu
• 7: 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

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Clustering

General Terms:
Algorithms, Experimentation, Management, Performance

Keywords:
data mining, dimensionality reduction, time series