Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the LowDistance Regime and Approximate Evaluation Dynamic time warping distance (DTW) is a widely used distance measure between time series. The best known algorithms for computing DTW run in near quadratic time, and conditional lower bounds prohibit the existence of significantly faster algorithms. The lower bounds do not prevent a faster algorithm for the special case in which the DTW is small, however. For an arbitrary metric space Sigma with distances normalized so that the smallest nonzero distance is one, we present an algorithm which computes operatornamedtw(x, y) for two strings x and y over Sigma in time O(n cdot operatornamedtw(x, y)). We also present an approximation algorithm which computes operatornamedtw(x, y) within a factor of O(nepsilon) in time tildeO(n2  epsilon) for 0 u003c epsilon u003c 1. The algorithm allows for the strings x and y to be taken over an arbitrary wellseparated tree metric with logarithmic depth and at most exponential aspect ratio. Extending our techniques further, we also obtain the first approximation algorithm for edit distance to work with characters taken from an arbitrary metric space, providing an nepsilonapproximation in time tildeO(n2  epsilon), with high probability. Additionally, we present a simple reduction from computing edit distance to computing DTW. Applying our reduction to a conditional lower bound of Bringmann and Kunnemann pertaining to edit distance over 0, 1, we obtain a conditional lower bound for computing DTW over a three letter alphabet (with distances of zero and one). This improves on a previous result of Abboud, Backurs, and Williams. With a similar approach, we prove a reduction from computing edit distance to computing longest LCS length. This means that one can recover conditional lower bounds for LCS directly from those for edit distance, which was not previously thought to be the case.

Invariant Subspace Learning for Time Series Data Based on Dynamic Time Warping Distance Abstract   Lowdimensional and compact representation of time series data is of importance for mining and storage. In practice, time series data are vulnerable to various temporal transformations, such as shift and temporal scaling, however, which are unavoidable in the process of data collection. If a learning algorithm directly calculates the difference between such transformed data based on Euclidean distance, the measurement cannot faithfully reflect the similarity and hence could not learn the underlying discriminative features. In order to solve this problem, we develop a novel subspace learning algorithm based on dynamic time warping (DTW) distance which is an elastic distance defined in a DTW space. The algorithm aims to minimize the reconstruction error in the DTW space. However, since DTW space is a semipseudo metric space, it is difficult to generalize common subspace learning algorithms for such semipseudo metric spaces. In this work, we introduce warp operators with which DTW reconstruction error can be approximated by reconstruction error between transformed series and their reconstructions in a subspace. The warp operators align time series data with their linear representations in the DTW space, which is in particular important for misaligned time series, so that the subspace can be learned to obtain an intrinsic basis (dictionary) for the representation of the data. The warp operators and the subspace are optimized alternatively until reaching equilibrium. Experiments results show that the proposed algorithm outperforms traditional subspace learning algorithms and temporal transforminvariance based methods (including SIDL, Kernel PCA, and SPMC et. al), and obtains competitive results with the stateoftheart algorithms, such as BOSS algorithm.