Dynamic Sub-Sequence Warping: A Representation-Based Similarity Measure for Long Time Series

Abstract Dynamic time warping (DTW), a typical elastic similarity measure that compares one-to-many points, has been proven effective for various time-series data mining tasks. However, it requires a quadratic time complexity $$O(n^2)$$ proportional to the length of time-series data, which undermines its applications involving long time series. In this paper, a representation-based similarity measure called Dynamic Sub-Sequence Warping (DSSW) is proposed. Instead of working on the raw data directly, we perform data representation to extract the distributional features of time series. Then, the similarity between two time series is measured by aligning the corresponding sub-sequences composed of the extracted features. We evaluate the proposed method through a supervised learning task on extensive real-world datasets. The results show that DSSW outperforms the prevalent DTW-based methods in terms of precision, and achieves one order of magnitude faster execution time on average compared with DTW.