Deducing for dynamic time warping distance

The current research achievements show that the dynamic time warping (DTW) is the best measure in most area of time series similarity measurements. However, the high time complexity for calculating DTW distance directly, and the fact that DTW does not satisfy the triangle inequality, render it impossible to deduce TWD quickly. Nowadays DTW optimizing methods are mainly devoted to designing low time complexity DTW low bound distances with low time complexity to accelerate time series comparison. Unfortunately, these DTW low bound distances cannot be deduced, either. Therefore, it must be compared one by one to compute time series similarity, which has high I/O cost. A novel educible DTW low bound distance is thus proposed, along with a corresponding index building method and a similar time series query algorithm. It is the first research on the DTW deducing problem. Extended experiment results show that compared to current technologies, the proposed method is efficient in both time complexity and I/O cost.