Dynamic Time Warping and Geometric Edit Distance
Omer Gold, Micha Sharir · ACM Transactions on Algorithms · 2018
Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology. Consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points inX= Rdare long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional cased= 1, which is perhaps one of the most used in practice. In this article, we break the nearly 50-year-old quadratic time bound for computing DTW or GED between two sequences ofnpoints in R by presenting deterministic algorithms that run inO(n2log log logn/ log logn) time. Our algorithms can be extended to work also for higher-dimensional spaces Rd, for any constantd, when the underlying distance-metric dist is polyhedral (e.g.,L1,Linfin).