Exact Mean Computation in Dynamic Time Warping Spaces
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.
Code (0)
등록된 구현이 없습니다.
Tasks
BenchmarkingDynamic Time WarpingTime SeriesTime Series AnalysisSimilar Papers 제목 키워드 기반
On the Existence of a Sample Mean in Dynamic Time Warping Spaces
The concept of sample mean in dynamic time warping (DTW) spaces has been successfully applied to improve pattern recognition systems and generalize centroid-based clustering algorithms. Its existence has neither been pro…
ClusteringDynamic Time WarpingExact, Parallelizable Dynamic Time Warping Alignment with Linear Memory
Audio alignment is a fundamental preprocessing step in many MIR pipelines. For two audio clips with M and N frames, respectively, the most popular approach, dynamic time warping (DTW), has O(MN) requirements in both memo…
Dynamic Time WarpingGPUOTW: Optimal Transport Warping for Time Series
Dynamic Time Warping (DTW) has become the pragmatic choice for measuring distance between time series. However, it suffers from unavoidable quadratic time complexity when the optimal alignment matrix needs to be computed…
ClusteringDeep LearningDynamic Time WarpingTime SeriesMulti-Sample Dynamic Time Warping for Few-Shot Keyword Spotting
In multi-sample keyword spotting, each keyword class is represented by multiple spoken instances, called samples. A na\"ive approach to detect keywords in a target sequence consists of querying all samples of all classes…
AllDynamic Time WarpingKeyword SpottingExact Indexing of Time Series under Dynamic Time Warping
Dynamic time warping (DTW) is a robust similarity measure of time series. However, it does not satisfy triangular inequality and has high computational complexity, severely limiting its applications in similarity search …
Dynamic Time WarpingTime SeriesTime Series Analysis