Two-step Similarity Search Of Time Series Based On DTW Distance

Dynamic time warping (DTW) is an effective approach for similarity search of time series with different lengths and steps. It has been widely used in the field of similarity search of time series. However, the complexity of this method is too high to be directly applied to solve this problem. Therefore, this paper proposes a new two-step approach based on DTW distance for similarity search of time series. It should be run before calculating the real DTW distance, as the candidate set of small size is being selected from the whole dataset of large size through the process and we only accomplish the DTW calculation on the candidate set. That makes the complexity of whole algorithm greatly decreases.The first step is mapping the time series to a k-dimension space through dividing the range value according to the given time interval. The new distance function, measuring the similarity of two different sequences in this space, can be used for excluding some sequences from the candidate set, as this function value is less than the real DTW distance. With relatively low time complexity, it doesn't have the high pruning power as not considering the elements'sequences and warping width constraints. That's the reason this process is considered as the first step of the whole algorithm.The new bounds of DTW distance is introduced in the second step, including the upper and lower bound. It can get the approximation to the real DTW distance in two different dirrections, which are actually the criterion for selecting time series candidates. The new lower bound function is more appropriate to the real DTW distance than other exsiting ones, and the new upper bound can be gotten also. Although it has the high time complexity, the new lower and upper bound method can be used as the second step of the whole algorithm with the increased pruning power. The two-step method gets the balance between time complexity and pruning power. This approach makes full use of the advantages of the two different functions by combining them in sequence. The results of simulation experiments show us that both these two steps are better than other ways of same kind and the two-step method than the two independent steps.