<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>3854</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>252</pageFirst>
    <pageLast>291</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>33</volume>
    <type>article</type>
    <publisherName>Springer Nature</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-01-15</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Exact mean computation in dynamic time warping spaces</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Data Mining and Knowledge Discovery</parentTitle>
    <identifier type="doi">10.1007/s10618-018-0604-8</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="BegutachtungStatus">peer-reviewed</enrichment>
    <licence>Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG</licence>
    <author>Markus Brill</author>
    <author>Till Fluschnik</author>
    <author>Vincent Froese</author>
    <author>Brijnesh Jain</author>
    <author>Rolf Niedermeier</author>
    <author>David Schultz</author>
    <collection role="institutes" number="FakIM">Fakultät Informatik und Mathematik</collection>
    <collection role="othpublikationsherkunft" number="">Externe Publikationen</collection>
    <collection role="othforschungsschwerpunkt" number="16315">Information und Kommunikation</collection>
  </doc>
</export-example>
