# Exact Mean Computation in Dynamic Time Warping Spaces

arXiv: https://arxiv.org/abs/1710.08937 · HTML: https://mlsanity.com/paper/1710.08937/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2017.

## Built on by (most cited first, 4 of 4)

- [Adversarial Imitation Learning with Trajectorial Augmentation and Correction](https://mlsanity.com/paper/2103.13887/) (2021)
- [Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering](https://mlsanity.com/paper/2411.17838/) (2024)
- [Accurate shape and phase averaging of time series through Dynamic Time Warping](https://mlsanity.com/paper/2109.00978/) (2021)
- [Time Elastic Neural Networks](https://mlsanity.com/paper/2405.17516/) (2024)

## Abstract (arXiv)

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'echet 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.