direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

 

Date
Speaker
Location
Language
02.05.2019
16:15
Vincent Froese
TEL 512
English

Back to the research colloquium site.

To top

Zusatzinformationen / Extras