An approach for fast subsequence matching through KMP algorithm in time series databases
Aijun Li, Yunhui Liu, Yingjian Qi, Siwei Luo · 2002
Sequence matching in time series databases is one of the most important data mining applications. In this paper, we focus on subsequence matching. We propose an efficient approach to compare time series. To simplify the searching process, we first use the KMP algorithm to carry through rough sequence matching. As KMP is a typical algorithm for string matching, we must transform time series into 0-1 string inspired by literature (Keogh and Pazzani,1999); then we quickly. search all rough similar subsequences from major sequence and finally, to reduce the dimension of raw time series data, we use Harr wavelet transform to represent the sequence to be compared and use WT (Wavelet Transformations) coefficients to compute the similarity of two sequences. That we carry out rough matching at first may reduce the numbers of WT and quicken the whole subsequence matching process.