Exact mean computation in dynamic time warping spaces

DOI10.1007/S10618-018-0604-8zbMATH Open1458.62196arXiv1710.08937OpenAlexW2963332138WikidataQ128825205 ScholiaQ128825205MaRDI QIDQ2218328FDOQ2218328

Authors: Yanyan Li 

Publication date: 15 January 2021

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1710.08937

Recommendations

• Approximating length-restricted means under dynamic time warping
• scientific article; zbMATH DE number 7651119
• An average-compress algorithm for the sample mean problem under dynamic time warping
• Fast exact dynamic time warping on run-length encoded time series
• Dynamic time warping under translation: approximation guided by space-filling curves

zbMATH Keywords

dynamic programmingtime series analysis[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Fr%EF%BF%BD%EF%BF%BDchet+function&go=Go Fr��chet function]exact exponential-time algorithmempirical evaluation of heuristics

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Analysis of algorithms (68W40)

Cites Work

• Benchmarking optimization software with performance profiles.
• Dynamic programming algorithm optimization for spoken word recognition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms on Strings, Trees and Sequences
• The complexity of multiple sequence alignment with SP-score that is a metric
• Title not available (Why is that?)
• A global averaging method for dynamic time warping, with applications to clustering
• Summarizing a set of time series by averaging: from Steiner sequence to compact multiple alignment
• Fast and Accurate Time-Series Clustering
• Dynamic time warping and geometric edit distance: breaking the quadratic barrier
• Hardness results for the center and median string problems under the weighted and unweighted edit distances

Cited In (9)

• Fast exact dynamic time warping on run-length encoded time series
• Times series averaging and denoising from a probabilistic perspective on time-elastic kernels
• Tight hardness results for consensus problems on circular strings and time series
• A global averaging method for dynamic time warping, with applications to clustering
• Summarizing a set of time series by averaging: from Steiner sequence to compact multiple alignment
• On computing exact means of time series using the move-split-merge metric
• An average-compress algorithm for the sample mean problem under dynamic time warping
• Approximating length-restricted means under dynamic time warping
• Sufficient conditions for the existence of a sample mean of time series under dynamic time warping

Uses Software

• GitHub
• DBA
• soft-DTW

This page was built for publication: Exact mean computation in dynamic time warping spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218328)