@article{BrillFluschnikFroeseetal., author = {Brill, Markus and Fluschnik, Till and Froese, Vincent and Jain, Brijnesh and Niedermeier, Rolf and Schultz, David}, title = {Exact mean computation in dynamic time warping spaces}, series = {Data Mining and Knowledge Discovery}, volume = {33}, journal = {Data Mining and Knowledge Discovery}, publisher = {Springer Nature}, doi = {10.1007/s10618-018-0604-8}, pages = {252 -- 291}, abstract = {Averaging time series under dynamic time warping is an important tool for improving nearest-neighbor classifiers and formulating centroid-based clustering. The most promising approach poses time series averaging as the problem of minimizing a Fr{\´e}chet function. Minimizing the Fr{\´e}chet function is NP-hard and so far solved by several heuristics and inexact strategies. Our contributions are as follows: we first discuss some inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Then we propose an exponential-time dynamic program for computing a global minimum of the Fr{\´e}chet function. The proposed algorithm is useful for benchmarking and evaluating known heuristics. In addition, we present an exact polynomial-time algorithm for the special case of binary time series. Based on the proposed exponential-time dynamic program, we empirically study properties like uniqueness and length of a mean, which are of interest for devising better heuristics. Experimental evaluations indicate substantial deficits of state-of-the-art heuristics in terms of their output quality.}, language = {en} }