The Library
Exact mean computation in dynamic time warping spaces
Tools
Brill, Markus, Fluschnik, Till, Froese, Vincent, Jain, Brijnesh, Niedermeier, Rolf and Schultz, David (2019) Exact mean computation in dynamic time warping spaces. Data Mining and Knowledge Discovery, 33 (1). pp. 252-291. doi:10.1007/s10618-018-0604-8 ISSN 1384-5810.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s10618-018-0604-8
Abstract
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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | Data Mining and Knowledge Discovery | ||||||||
Publisher: | Springer | ||||||||
ISSN: | 1384-5810 | ||||||||
Official Date: | 15 January 2019 | ||||||||
Dates: |
|
||||||||
Volume: | 33 | ||||||||
Number: | 1 | ||||||||
Page Range: | pp. 252-291 | ||||||||
DOI: | 10.1007/s10618-018-0604-8 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |