  Computing an accurate mean of a set of time series is a critical task in
applications like nearest-neighbor classification and clustering of time
series. While there are many distance functions for time series, the most
popular distance function used for the computation of time series means is the
non-metric dynamic time warping (DTW) distance. A recent algorithm for the
exact computation of a DTW-Mean has a running time of
$\mathcal{O}(n^{2k+1}2^kk)$, where $k$ denotes the number of time series and
$n$ their maximum length. In this paper, we study the mean problem for the
move-split-merge (MSM) metric that not only offers high practical accuracy for
time series classification but also carries of the advantages of the metric
properties that enable further diverse applications. The main contribution of
this paper is an exact and efficient algorithm for the MSM-Mean problem of time
series. The running time of our algorithm is $\mathcal{O}(n^{k+3}2^k k^3 )$,
and thus better than the previous DTW-based algorithm. The results of an
experimental comparison confirm the running time superiority of our algorithm
in comparison to the DTW-Mean competitor. Moreover, we introduce a heuristic to
improve the running time significantly without sacrificing much accuracy.
