Exact Mean Computation in Dynamic Time Warping Spaces
This solves a computational bottleneck for researchers analyzing time series, but it is incremental as it builds on existing methods to improve accuracy.
The paper addresses the problem of computing exact mean series in dynamic time warping spaces, which is challenging and previously handled heuristically, by providing an exact dynamic program for benchmarking and revealing deficits in state-of-the-art heuristics.
Dynamic time warping constitutes a major tool for analyzing time series. In particular, computing a mean series of a given sample of series in dynamic time warping spaces (by minimizing the Fréchet function) is a challenging computational problem, so far solved by several heuristic and inexact strategies. We spot some inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Our contributions comprise an exact dynamic program computing a mean (useful for benchmarking and evaluating known heuristics). Based on this dynamic program, we empirically study properties like uniqueness and length of a mean. Moreover, experimental evaluations reveal substantial deficits of state-of-the-art heuristics in terms of their output quality. We also give an exact polynomial-time algorithm for the special case of binary time series.