• search hit 10 of 96
Back to Result List

Exact mean computation in dynamic time warping spaces

  • 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échet function. Minimizing the Fré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é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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Markus Brill, Till Fluschnik, Vincent Froese, Brijnesh JainORCiD, Rolf Niedermeier, David Schultz
DOI:https://doi.org/10.1007/s10618-018-0604-8
Parent Title (English):Data Mining and Knowledge Discovery
Publisher:Springer Nature
Document Type:Article
Language:English
Year of first Publication:2019
Release Date:2022/05/01
Volume:33
First Page:252
Last Page:291
Institutes:Fakultät Informatik und Mathematik
Begutachtungsstatus:peer-reviewed
Publication:Externe Publikationen
research focus:Information und Kommunikation
Licence (German):Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG