direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Averaging Time Series Under Dynamic Time Warping: Hardness and Experiments

Vincent Froese (TU Berlin)


The dynamic time warping distance is a well-known tool for time series mining. Computing a mean in dynamic time warping spaces is a challenging computational problem (solved by heuristics in practice) whose complexity status was so far unresolved.

We show that it is NP- and W[1]-hard, and that a recent dynamic programming algorithm is essentially optimal assuming the Exponential Time Hypothesis. In this context, we study a circular string alignment problem which serves as a key for our hardness reductions and is of independent (practical) interest in molecular biology. We also present experimental results about dynamic time warping means which provide some insights for devising better heuristics.


Vincent Froese
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras