Sparsification of the Alignment Path Search Space in Dynamic Time\n Warping

Abstract

Temporal data are naturally everywhere, especially in the digital era that\nsees the advent of big data and internet of things. One major challenge that\narises during temporal data analysis and mining is the comparison of time\nseries or sequences, which requires to determine a proper distance or\n(dis)similarity measure. In this context, the Dynamic Time Warping (DTW) has\nenjoyed success in many domains, due to its 'temporal elasticity', a property\nparticularly useful when matching temporal data. Unfortunately this\ndissimilarity measure suffers from a quadratic computational cost, which\nprohibits its use for large scale applications. This work addresses the\nsparsification of the alignment path search space for DTW-like measures,\nessentially to lower their computational cost without loosing on the quality of\nthe measure. As a result of our sparsification approach, two new\n(dis)similarity measures, namely SP-DTW (Sparsified-Paths search space DTW) and\nits kernelization SP-K rdtw (Sparsified-Paths search space K rdtw kernel) are\nproposed for time series comparison. A wide range of public datasets is used to\nevaluate the efficiency (estimated in term of speed-up ratio and classification\naccuracy) of the proposed (dis)similarity measures on the 1-Nearest Neighbor\n(1-NN) and the Support Vector Machine (SVM) classification algorithms. Our\nexperiment shows that our proposed measures provide a significant speed-up\nwithout loosing on accuracy. Furthermore, at the cost of a slight reduction of\nthe speedup they significantly outperform on the accuracy criteria the old but\nwell known Sakoe-Chiba approach that reduces the DTW path search space using a\nsymmetric corridor.\n