A Research On The Indexing Method Of Time Series Based On Dynamic Planning And DTW Warping Path

The time series is now widely used in the fields of finance, biologic and so on. More and more researchers focus on it. Among its many areas of research, the problem of searching similar time series has been widely studied. This problem is often converted to the problem of time series indexing. While Dynamic Time Warping (DTW) is a powerful method to measure the similarity between two times series, it’s hard to be used to index time series directly because it doesn’t obey the triangular inequality. Facing this problem, lower-bound method is used to make exact indexing. The distance of low-bound is strictly less or equal than that of DTW. The tightness of low-bound is the key factor that affect the performance of indexing.In the paper, we reviewed some other researchers’work on time series indexing and present a new indexing technique based on dynamic programming. We build a new kind of indexing tree and a special, multi-segment indexing structure based on DTW. Based on the special indexing structure, we proposed the method of low-bound distance between query sequence and the structure. Finally, a searching process is available based on the low-bound distance method. At the same time, in order to build a more effective indexing tree, we also proposed a new idea on calculating the center of two pieces of time series. And we used it to extend the DBA method. we demonstrate that our new method on central time series is more effective and when the wrapping window is large, our indexing method has a more tight low-bound and has better effectiveness on indexing than most of existing indexing methods.