# On Computing Exact Means of Time Series Using the Move-Split-Merge Metric

Jana Holznigenkemper111 Dept. of Mathematics and Computer Science, University
of Marburg, Germany, {holznigenkemper, komusiewicz<EMAIL_ADDRESS>marburg.de , Christian Komusiewicz∗, Bernhard Seeger∗

###### Abstract

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^{k}k)$, 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.

Keywords— Time Series Means, Time Series Metrics, Dynamic Programming, Exact
Algorithm

##  1 Introduction

Time series databases have gained much attention in academia and industry due
to demands in many new challenging applications like Internet of Things (IoT),
bioinformatics, social and system monitoring. In particular, because of the
emergence of IoT, the requirement for developing dedicated systems [32]
supporting time series as a first-class citizen has increased recently. In
addition to supporting fundamental database operations like filters and joins,
analytical operations like clustering and classification are highly relevant
in time series databases.

The analysis of time series like clustering largely depends on the underlying
distance functions. In a recent study, Paparrizos et al. [34] re-examined the
impact of 71 distance functions on classification for many datasets. While
_dynamic time warping (DTW)_ and related functions [8] had the reputation of
being the best choice,

Paparrizos et al. [34] found DTW performing inferior for time series
classification in comparison to many other elastic distance functions. Among
those is the _move-split-merge ( MSM) metric_ [19]. It works similarly to the
Levensthein distance [2] by transforming one time series into another using
three types of operations. A move operation changes the value of a data point,
a merge operation fuses two consecutive points with equal values into one, and
a split operation splits a point into two adjacent points with the same value.
In addition to its superiority to DTW, MSM offers another significant
advantage: it satisfies the properties of a mathematical metric, and thus it
is ready-to-use for metric indexing [15] and algorithms that presume the
triangle inequality.

Partition-based algorithms such as k-means clustering are among the best
methods for clustering time series [29]. One of the fundamental problems of
k-means clustering for time series is how to compute a mean for a set of time
series. Brill et al. [31] studied the problem for DTW and developed an
algorithm computing an exact mean of $k$ time series in
$\mathcal{O}(n^{2k+1}2^{k}k)$ time, where $n$ is the maximum length of an
input time series. To the best of our knowledge, the mean problem of time
series has not been addressed for other distance functions like the MSM metric
so far.

In this paper, we examine the mean problem of time series for the MSM metric.
The mean $m$ of a set $X$ of input time series is a time series that minimizes
the sum of the distances to the time series in $X$ regarding the MSM metric.
In the following, we use MSM-Mean and DTW-Mean to denote the mean of the MSM
metric and DTW distance function, respectively.

An example of MSM-Mean is depicted in Figure 1. It comprises four sample time
series from the data set _Italy Power Demand_ of the UCR time series archive
[21] with their respective MSM-Mean. In contrast to DTW-Mean, we show that
MSM-Mean consists of values only present in the underlying time series. This
observation is crucial for the design and efficiency of our algorithm. We
prove that the running time of our algorithm is
$\mathcal{O}(n^{k+3}2^{k}k^{3})$, thus faster than the DTW-based competitor
[31].

In summary, our contributions are:

  * •

We give new essential characteristics of the MSM metric. We first prove that
there always exists an optimal transformation graph that is a forest to
further specify the values of some crucial nodes within this forest.

  * •

We show that MSM-Mean only consists of data points that are present in at
least one time series of the input set.

  * •

We develop a dynamic program computing the exact MSM-Mean of $k$ input time
series achieving a better theoretical running time than its competitor DTW-
Mean.

  * •

In experiments on samples of real-world time series, we show that the
practical running time of MSM-Mean is faster than DTW-Mean.

  * •

We present preliminary heuristics computing MSM-Mean in significantly faster
running time without sacrificing much accuracy.

The remainder of the paper is structured as follows. Section 2 reviews related
work. In Section 3, we give some important preliminaries for the MSM metric
and formulate the MSM-Mean problem. Then, in Section 4, we introduce some new
properties of the MSM metric to prove at the end of the section that there
always exists a mean consisting of data points of the input time series. The
dynamic program for the exact MSM-Mean algorithm is given in Section 5. We
experimentally evaluate our approach, discuss various heuristics, and compare
it to the DTW-Mean algorithm in Section 6, and conclude in Section 7.

Figure 1: MSM-Mean of four time series from the Italy Power Demand data set
containing time series of length $n=24$.

##  2 Related Work

For the exploratory analysis of time series, clustering is used to discover
interesting patterns in time series datasets [9]. Much research has been done
in this area [11]. The surveys [20, 18] give a recent overview of many
methods. The problem of mean computation is discussed for Euclidean distance
and for the DTW distance, but not for the MSM metric.

Moreover, the use of classification methods is indispensable for accurate time
series analysis [33]. The temporal aspect of time series has to be taken into
account for clustering and classification, though finding a representation of
a set of time series is a challenging task. Determining accurate means of time
series is crucial for partitioning clustering approaches [13] like k-means
[3], where the prototype of a cluster is a mean of its objects, and for
nearest-neighbor classification [23]. These methods are based on the choice of
the underlying distance function. Among the existing time series distance
measures [34], the DTW distance [5] is a very important measure with
application in, e.g., similarity search [12], speech recognition [6], or gene
expression [10]. We now give an overview of mean computation methods using the
DTW distance.
Besides the exact DTW-Mean algorithm [31] that minimizes the Fréchet function
[1], there are many heuristics trying to address this problem. Some approaches
first compute a multiple alignment of $k$ input time series and then average
the aligned time series column-wise [14, 17]. _DTW barycenter averaging (DBA)_
[16] is a heuristic strategy that iteratively refines an initially average
sequence in order to minimize its square DTW-distance to the input time
series. Other approaches exploit the properties of the Fréchet function [27,
30]. Their methods are based on the observation that the Fréchet function is
Lipschitz continuous and thus differentiable almost everywhere. Cuturi et al.
[27] use a smoothed version of the DTW-distance to obtain a differentiable
Fréchet DTW-distance. Brill et al. [31] showed that none of the aforementioned
approaches is sufficiently accurate compared to the exact method. Since
clustering methods based on partitioning rely on cluster prototype
determination [20], it is necessary to compute an accurate mean. All these
observations make it indispensable to consider the problem for other distance
functions, like the MSM metric.

The MSM metric is already investigated for classification. One of the first
studies of the MSM metric concerning its application for classification
problems was by Stefan et al. [19]. They perform their tests on 20 data sets
of the UCR archive [21]. The MSM distance is tested against the DTW distance,
the constrained DTW distance, the edit distance on real sequence and the
Euclidean distance. For a majority of the tests, the MSM distance performs
better than the compared measures. There have been further studies of the
accuracy of different time series distance measures regarding 1-NN
classification problems [25, 22]. Bagnall et al. [25] also conclude that the
MSM distance leads to better accuracy results than DTW but worse running time.
All these studies come to a similar result as the most recent study of
Paparrizos et al. [34]. To the best of our knowledge, there are no studies
that investigate and extend the theoretical concepts and applications of the
MSM distance.

The subject of time series, also known as data series, has attracted attention
within the database research domain recently, see [28] for a recent survey.
There are time series data bases, also known as event stores, that are
specially designed for the analysis of time series [24, 32]. These systems
rarely support clustering, but focus on supporting the basic building blocks
for query processing.

Since the MSM distance obeys all properties of a mathematical metric,
especially the triangle inequality, it also applies to problems like metric
indexing [26, 15]. In fact, metric indexing also requires the computation of
pivots that is closely related to the mean. However, pivots belong to the
underlying data set, while the mean (of a time series) is generally a newly
generated object.

##  3 Preliminaries

Let us first introduce our notation and problem definition. For
$k\in\mathds{N}$, let $[k]:=\\{1,\ldots,k\\}$. A _time series_ of length $n$
is a sequence $x=(x_{1},\ldots,x_{n})$, where each _data point_ , in short
_point_ , $x_{i}$ is a real number. Let $V(x)=\\{x_{i}~{}|~{}x~{}\in~{}x\\}$
be the set of all values of points of $x$. For $i<j$, the point $x_{i}$ is a
_predecessor_ of the point $x_{j}$ and the point $x_{j}$ is a _successor_ of
the point $x_{i}$. For a set of time series $X=\\{x^{(1)},\ldots,x^{(k)}\\}$,
the $i$th point of the $j$th time series of $X$ is denoted as $x_{i}^{(j)}$;
time series $x^{(j)}$ has length $n_{j}$. Further let
$V(X)=\cup_{j\in[k]}V(x^{(j)})=\\{v_{1},\ldots,v_{r}\\}$ be the set of the
values of all points of all time series in $X$.

###  3.1 Move-Split-Merge Operations

We now define the MSM metric, following the notation of Stefan et al. [19],
and the MSM-Mean problem. The MSM metric allows three transformation
operations to transfer one time series into another: _move, split_ , and
_merge_ operations. For time series $x=(x_{1},\ldots,x_{n})$ a move transforms
a point $x_{i}$ into $x_{i}+w$ for some $w\in\mathds{R}$, that is,
$\operatorname{Move}_{i,w}(x)\coloneqq(x_{1},\ldots,x_{i-1},x_{i}+w,x_{i+1},\ldots,x_{n})$,
with cost $\operatorname{Cost}(\operatorname{Move}_{i,w})=|w|$. Informally, we
say that there is a _move at point $x_{i}$ to another point_ $x_{i}~{}+~{}w$.
The split operation splits the $i$th element of $x$ into two consecutive
points. A split at point $x_{i}$ is defined as
$\operatorname{Split}_{i}(x)\coloneqq(x_{1},\ldots,x_{i-1},x_{i},x_{i},x_{i+1},\ldots,x_{n}).$

A merge operation may be applied to two consecutive points of equal value. For
$x_{i}=x_{i+1}$, it is given by
$\operatorname{Merge}_{i}(x)\coloneqq(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n}).$
We say that $x_{i}$ and $x_{i+1}$ _merge to a point_ $z$. Split and merge
operations are inverse operations. Their costs are assumed to be equal and
determined by a given nonnegative constant
$c=\operatorname{Cost}(\operatorname{Split}_{i})=\operatorname{Cost}(\operatorname{Merge}_{i})$.
A _sequence of transformation operations_ is given by
$\mathbb{S}=(S_{1},\ldots,S_{s})$, where
$S_{j}\in\\{\operatorname{Move}_{i_{j},w_{j}},\operatorname{Split}_{i_{j}},\operatorname{Merge}_{i_{j}}\\}$.
A _transformation_ $T(x,\mathbb{S})$ of a time series $x$ for a given sequence
of transformation operations $\mathbb{S}$ is defined as
$T(x,\mathbb{S})\coloneqq T(S_{1}(x),(S_{2},\ldots,S_{s}))$. If $\mathbb{S}$
is empty, we define $T(x,\emptyset)\coloneqq x$. The cost of a sequence of
transformation operations $\mathbb{S}$ is given by the sum of all individual
operations cost, that is,
$\operatorname{Cost}(\mathbb{S})\coloneqq\sum_{S\in\mathbb{S}}\operatorname{Cost}(S).$
We say that $\mathbb{S}$ transforms $x$ to $y$ if $T(x,\mathbb{S})=y$. We call
a transformation an _optimal transformation_ if it has minimal cost
transforming $x$ to $y$. The _MSM distance_ $d(x,y)$ between two time series
$x$ and $y$ is defined as the cost of an optimal transformation. The distance
$D(X,y)$ of multiple time series $X=\\{x^{(1)},\ldots,x^{(k)}\\}$ to a time
series $y$ is given by $D(X,y)=\sum_{x\in X}d(x,y).$ A _mean_ $m$ of a set of
time series $X$ is defined as the time series with minimum distance to $X$,
that is, $m=\operatorname*{arg\,min}_{z\in\mathcal{Z}}D(X,z)$, where
$\mathcal{Z}$ is the set of all finite time series. The problem of computing a
mean is thus defined as follows:

MSM-Mean
Input: A set of time series $X=\\{x^{(1)},\ldots,x^{(k)}\\}$.
Output: A time series $m$ such that
$m=\operatorname*{arg\,min}_{z\in\mathcal{Z}}D(X,z)$.

Before we regard the MSM-Mean problem in more detail, we will introduce the
concept of _transformation graphs_ to describe the structure of a
transformation $T(x,\mathbb{S})=y$.

###  3.2 Transformation graphs

The transformation $T(x,\mathbb{S})=y$ can be described by a directed acyclic
graph $G_{\mathbb{S}}(x,y)$, the _transformation graph_ , with _source nodes_
$N(x)=\\{u_{1},\ldots,u_{m}\\}$ and _sink nodes_
$N(y)=\\{v_{1},\ldots,v_{n}\\}$, where a node $u_{i}$ represents the point
$x_{i}$ and the node $v_{j}$ represents the point $y_{j}$. All nodes which are
neither source nor sink nodes are called _intermediate nodes_. If the time
series and operation sequence are clear from context, we may write $G$ instead
of $G_{\mathbb{S}}(x,y)$. Each node in the node set $V$ of $G$ is associated
with a value given by a function
$\operatorname{val}:~{}V\rightarrow\mathds{R}$. For source and sink nodes we
have $\operatorname{val}(u_{i})=x_{i}$ and $\operatorname{val}(v_{j})=y_{j}$.
Each intermediate node is also associated with a value. The edges represent
the transformation operations of $\mathbb{S}$. To create a transformation
graph, for each operation in $\mathbb{S}$ a respective _move edge_ or two
_split_ , or _merge edges_ are added to the graph. A move edge can be further
specified as an _increasing (inc-)_ or _decreasing (dec-)_ edge if the move
operation adds a positive or negative value to the value of the parent node,
respectively. An edge can be either a move, split or merge edge. If a node
$\alpha$ is connected to a node $\beta$ by a split edge and $\beta$ is a child
of $\alpha$, then there exists a node $\gamma\neq\beta$ to which $\alpha$ is
connected by a split edge and which is a child of $\alpha$. If the nodes
$\alpha$ and $\beta$ are connected by a merge edge and $\alpha$ is a parent of
$\beta$, then there exists a node $\gamma\neq\alpha$ which is connected to
$\beta$ by a merge edge and is a parent of $\beta$. Moreover, for the split
and the merge case, it holds that
$\operatorname{val}(\alpha)=\operatorname{val}(\beta)=\operatorname{val}(\gamma)$.

Given a set of sequence of operations $\mathbb{S}$, the transformation graph
$G_{\mathbb{S}}(x,y)$ is unique. Given a transformation graph $G$, it may be
derived from different sequences of operations since a sequence $\mathbb{S}$
is only partially ordered. Taking the example of a transformation graph (see
Figure 2), that means, that for example the move operation between the node
$u_{1}$ and $\alpha$ and the move operation between $u_{4}$ and $v_{3}$ are
interchangeable.

Figure 2: Optimal transformation graph of $x=(4,5,5,10)$ to $y=(10,7,8)$ for
$c=0.1$. Move edges are colored in red in this work. The cost of a move edge
is the difference between the source and the target point. We have total cost
merge and split cost $3c$ and move cost of 8. Hence, the distance between $x$
and $y$ is $d(x,y)=8.3$.

A _transformation path_ , in short _path_ , in $G_{\mathbb{S}}(x,y)$ is a
directed path from a source node $u_{i}\in N(x)$ to a sink node $v_{j}\in
N(y)$. We say that $u_{i}$ is _aligned_ to $v_{j}$. A path can be further
characterized by its sequence of edge labels. For example, in Figure 2, the
path from $u_{1}$ to $v_{2}$ is an inc-merge-inc-split path. Analogously, we
say that the path consists of consecutive inc-merge-inc-split edges.

A transformation path is _monotonic_ if the move edges on this path are only
inc- or only dec-edges. A monotonic path may be specified as _increasing_ or
_decreasing_. A transformation is _monotonic_ if the corresponding
transformation graph only contains monotonic paths. A transformation graph is
_optimal_ if it belongs to an optimal transformation. Two transformation
graphs are _equivalent_ if they have the same sink and source nodes.

In the next section, we recap some known properties about the transformation
graph and extend them proving some new essential characteristics.

###  3.3 Properties of Transformation Graphs

In the following, we summarize some important known properties about the
transformation graph by Stefan et al. [19]. The first lemma states that there
exists an optional transformation graph without split and merge edges that
occur directly after another on a path.

######  Lemma 1 (Proposition 2 [19]).

For any two time series $x$ and $y$, there exists an optimal sequence of
transformation operations $\mathbb{S}$ such that $G_{\mathbb{S}}(x,y)$
contains no consecutive merge-split or split-merge edges.

By construction, two consecutive move-move edges are not useful, since they
can be combined into one move edge. We extend Lemma 1 to further path
restrictions in an optimal transformation graph. That is, that there exists an
optimal transformation graph without paths containing consecutive split-move-
merge edges.

######  Lemma 2.

For any two time series $x$ and $y$, there exists an optimal sequence of
transformation operations $\mathbb{S}$ such that $G_{\mathbb{S}}(x,y)$
contains no consecutive split-move-merge edges.

###### Proof.

Assume an optimal transformation graph $G_{\mathbb{S}}(x,y)$ including split-
move-merge edges. Since the underlying set of transformation operations
$\mathbb{S}$ of $G$ is partially ordered, we can reorder the operations in
$\mathbb{S}$, choosing an order, where split, move and merge operations are
directly applied after one another. Figure 3 shows two different possibilities
how consecutive split-move-merge edges may be contained in a transformation
graph.
Case I: We consider a split at node $\alpha$ to the nodes $\alpha^{\prime}$
and $\alpha^{\prime\prime}$ where
$\operatorname{val}(\alpha)=\operatorname{val}(\alpha^{\prime})=\operatorname{val}(\alpha^{\prime\prime})$.
It is followed by two move edges from $\alpha^{\prime}$ to $\beta^{\prime}$
and from $\alpha^{\prime\prime}$ to $\beta^{\prime\prime}$ and a merge of
$\beta^{\prime}$ and $\beta^{\prime\prime}$ (see Figure 3a). Therefore, the
values added to $\operatorname{val}(\alpha)$ have to be equal on both move
edges, that is a value $w\in\mathds{R}$. The cost of these transformation
operations are $2c+2|w|$. Consider replacing the two split-move-merge edges
with one direct move edge from $\alpha$ to $\beta$ adding $w$ to
$\operatorname{val}(\alpha)$ (see Figure 3b). This replacement leads to an
equivalent transformation with cost $|w|<2c+2|w|$. This is a contradiction to
our assumption that $G$ is optimal.
Case II: Consider the part of a transformation graph in Figure 3c. There is a
split at $\alpha$ to $\alpha^{\prime}$ and $\alpha^{\prime\prime}$. The node
$\alpha^{\prime\prime}$ is connected by a move edge to $\beta^{\prime}$ adding
a value $w$ to $\operatorname{val}(\alpha^{\prime\prime})$. The node
$\beta^{\prime}$ merges with $\beta^{\prime\prime}$ to $\beta$. Deleting the
split-move-merge edge and editing the part of the graph as shown in Figure 3d
leads to an equivalent transformation graph, saving cost of $2c+|w|$. This is
a contradiction to our assumption that $G$ is optimal. ∎

Figure 3: a) First possibility of a transformation graph including consecutive
split-move-merge edges. b) Equivalent transformation graph to a). c) Second
possibility of a transformation graph including consecutive split-move-merge
edges. d) Equivalent transformation graph to c)

The next lemma states that there is always an optimal monotonic
transformation.

######  Lemma 3 (Monotonicity lemma [19]).

For any two time series $x$ and $y$, there exists an optimal transformation
that converts $x$ into $y$ and that is monotonic.

Summarizing the above properties, there always exists an optimal
transformation graph only containing paths from source to sink nodes of the
following consecutive edge types:

Type 1:

move - move - $\cdots$ \- move - move

Type 2:

split/move - split/move - $\cdots$ \- split/move -split/move

Type 3:

merge/move - merge/move - $\cdots$ \- merge/move - merge/move

Type 4:

Type 3 - merge - move - split - Type 2

Note, that paths of Type 2 and Type 3 contain at least one split or merge
edge, respectively. In the following, we consider only transformation graphs
that contain only paths of Type 1–4. To identify independent transformation
operations, we decompose an optimal transformation graph into its weakly
connected components. A weakly connected component is a tree if its underlying
subgraph is a tree.

In the following, we give a more substantive view on those weakly connected
components which are trees (see Figure 4).
The first ones are _trees of Type 1_. These trees contain only paths of Type
1, that is, there is only one move edge in the tree connecting one source and
sink node (see Figure 4a). A weakly connected component containing only paths
of Type 2 has only one source node and at least two paths of Type 2, that is,
it has at least two sink nodes. It is a tree since all all nodes have indegree
1. We call these trees _trees of Type 2_ (see Figure 4b). _Trees of Type 3_
contain only paths of merge or move operations (Type 3). These trees have at
least two source nodes whose paths reach the same sink node. All nodes have
outdegree 1 (see Figure 4c). The last weakly connected component which is a
tree is a _tree of Type 4_. These trees include only paths of Type 4. They
contain only and at least two paths of Type 4, that is, that they have at
least two source and two sink nodes (see Figure 4d). For the following
sections, we need a more detailed description of Type-4-Trees. All source
nodes merge and move to some intermediate node $\sigma$. After $\sigma$, there
is a move to $\sigma^{*}$ with subsequent split and move edges leading to the
source nodes. All source and sink nodes of this tree are connected by one
single path which we call a _bottleneck_ with $\sigma$ as the _first
bottleneck node_ and $\sigma^{*}$ as the _second bottleneck node_. All nodes
above and including the first bottleneck node have outdegree 1. We call this
subgraph the _upper tree_ of $\sigma$. All nodes below and including the
second bottleneck node have indegree 1. We call this subgraph a _lower tree_
of $\sigma^{*}$.

Figure 4: All red edges are move operations. Black arrows are merge or split
edges. The dashed lines represent paths from one node to another without
specifying how many intermediate node are on them. a) Tree of Type 1. b) Tree
of Type 2. c) Tree of Type 3. d) Tree of Type 4.

The following lemma states that there always exists an optimal transformation
graph, where every weakly connected component is a tree of Type 1–4.

######  Lemma 4.

Let $x$ and $y$ be two time series. Then there exists an optimal
transformation graph $G_{\mathbb{S}}(x,y)$ such that its weakly connected
components are only trees of Type 1–4.

###### Proof.

We show that if a weakly connected component of a given optimal transformation
graph $G$ is not a tree of Type 1–3, then it has to be a tree of Type 4. We
consider a path of Type 4. In a path of Type 4 there is one part with
consecutive merge-move-split edges. Let $\sigma$ be the node between this
merge and move operation and $\sigma^{*}$ be the node between this move and
split operation. We add further move and merge operations to the part above
$\sigma$. We still have outdegree 1 of each node above $\sigma$. The same
applies for the part below $\sigma^{*}$: Adding further move and split
operations still leads to indegree 1 of each node below $\sigma^{*}$. Hence,
the subgraph of $G$ consisting of the edge from $\sigma$ to $\sigma^{*}$ and
all move or merge edges above $\sigma$ and all move or split edges below
$\sigma^{*}$ is a tree of Type 4. We now show that this tree structure cannot
be extended without violating our assumptions of the above Lemmas. Let
$\alpha$ be a node in the upper tree that is connected to a node
$\alpha^{\prime}$ that is neither in the upper nor in the lower tree. If
$\alpha$ is a source node or an intermediate node except of $\sigma$, the
first operation is a split, where one split edge is on the path to $\sigma$
and the other is on the path to $\alpha^{\prime}$. We get a contradiction to
Lemma 2, because the first path includes consecutive split-move-merge edges.
If $\alpha=\sigma$, we have again a split at $\alpha$, which is a
contradiction to Lemma 1 because we have a consecutive merge-split edge. The
same argumentation is applied for an extension of the lower tree, because it
is the symmetric case of the one we described. ∎

It follows that we can decompose an optimal transformation graph
$G_{\mathbb{S}}(x,y)$ into a sequence of distinct trees
$(\mathcal{T}_{1},\ldots,\mathcal{T}_{t})$. Each tree $\mathcal{T}_{i}$ has a
set of sink nodes $N_{\mathcal{T}_{i}}(x)$ and a set of source nodes
$N_{\mathcal{T}_{i}}(y)$. All nodes of $N_{\mathcal{T}_{i}}(x)$ and
$N_{\mathcal{T}_{i}}(y)$ are successors of $N_{\mathcal{T}_{i-1}}(x)$ and
$N_{\mathcal{T}_{i-1}}(y)$, respectively. We call a tree _monotonic_ if all
paths in the tree are monotonic. Further a tree may be specified as
_increasing_ or _decreasing_. Two trees are _equivalent_ if they have the same
set of source and sink nodes. The _cost of a tree $\mathcal{T}$_ is the sum of
the cost of all edges in the tree.

In the following, we denote an optimal transformation graph fulfilling all the
above properties as an _optimal transformation forest_.

##  4 Properties of the MSM Metric

As a main result of this section, we prove that for a set of time series $X$
there exists a mean $m$ such that all points of $m$ are points of at least one
time series of $X$. To this end, we first analyze the structure of trees of
optimal transformation forests. Some of the following results are only proven
for trees of Type 4 since these trees include all types of possible paths; as
a consequence the proofs for other tree types are simpler versions of the ones
for Type 4.

###  4.1 Properties of Alignment Trees

We first regard some properties of so-called _subtrees_ , which are
substructures of trees of Type 4.

####  4.1.1 Subtrees

Let $G_{\mathbb{S}}(x,y)$ be an optimal transformation forest. For an
intermediate node $\delta$ in $G$, that has two parent nodes connected to it
by a merge edge each, let $\mathcal{S}(\delta)$ be the _subtree of_ $\delta$
consisting of all source nodes of $G$ that have a path to $\delta$ and of all
nodes and edges on these paths. Each subtree has a set of source nodes
$N_{\mathcal{S}(\delta)}(x)$. Let
$N_{\mathcal{S}(\delta)}(x)=\\{u_{i},\ldots,u_{j}\\}$ be the source nodes of
$\mathcal{S}(\delta)$; we call $u_{i}$ the _start node of_
$\mathcal{S}(\delta)$ and $u_{j}$ the _end node of_ $\mathcal{S}(\delta)$. A
subtree is _increasing_ (_decreasing_) if all paths to $\delta$ are increasing
(decreasing). In the following, we will give some properties of subtrees. If
there are two move edges to some nodes $\alpha_{2}$ and $\beta_{2}$ that
merges to another node $\gamma$ (see Figure 5a), we first observe that these
two move edges cannot be both increasing or decreasing.

######  Lemma 5.

Let $G_{\mathbb{S}}(x,y)$ be an optimal transformation forest with nodes
$\alpha_{1},\alpha_{2},\beta_{1},\beta_{2}$ and $\gamma$ and move edges
between $\alpha_{1}$, $\alpha_{2}$ and $\beta_{1}$, $\beta_{2}$. If
$\alpha_{2}$ and $\beta_{2}$ merge to $\gamma$, then the edges between
$\alpha_{1}$, $\alpha_{2}$ and $\beta_{1}$, $\beta_{2}$ cannot be both
increasing or decreasing.

Figure 5: a) Merge structure of the (intermediate) nodes
$\alpha_{1},\alpha_{2},\beta_{1},\beta_{2}$ and $\gamma$. b) Equivalent tree
to the tree in a).

###### Proof.

Without loss of generality, we prove this assumption for increasing paths.
Assume towards a contradiction two inc-edges between $\alpha_{1}$ and
$\alpha_{2}$ and between $\beta_{1}$ and $\beta_{2}$ with
$\operatorname{val}(\alpha_{1})<\operatorname{val}(\beta_{1})$ (see Figure
5a). Since
$\operatorname{val}(\alpha_{2})=\operatorname{val}(\beta_{2})=\operatorname{val}(\gamma)$
the cost for these move operations are
$2\operatorname{val}(\gamma)-\operatorname{val}(\beta_{1})-\operatorname{val}(\alpha_{1})$.
We now consider a modified merge structure with an additional intermediate
node $\gamma_{1}$ with
$\operatorname{val}(\gamma_{1})~{}=~{}\operatorname{val}(\beta_{1})$ (see
Figure 5b). We now have an inc-edge from $\alpha_{1}$ to $\gamma_{1}$, which
merges with the new node $\beta_{1}$ to a new node $\gamma_{2}$. At
$\gamma_{2}$, there is an inc-edge to $\gamma$. The modified transformation
forest is equivalent to the old one, since the parent and children nodes of
the regarded nodes stay the same (see Figure 5). The cost for the modified
move operations are
$\operatorname{val}(\gamma)-\operatorname{val}(\beta_{1})+\operatorname{val}(\beta_{1})-\operatorname{val}(\alpha_{1})<2\operatorname{val}(\gamma)-\operatorname{val}(\beta_{1})-\operatorname{val}(\alpha_{1})$
since $\operatorname{val}(\beta_{1})<\operatorname{val}(\gamma)$. This is a
contradiction to $G$ being optimal. ∎

We now make two observations about the value of the node $\delta$ in a subtree
$\mathcal{S}(\delta)$. The first lemma states, that the value of $\delta$ is
equal to one value of the source nodes of $\mathcal{S}(\delta)$. Recall that
$u_{1},\ldots,u_{m}$ are the source nodes of $G_{\mathbb{S}}(x,y)$ with values
$x_{1},\ldots,x_{m}$.

######  Lemma 6.

Let $\mathcal{S}(\delta)$ be an increasing (decreasing) subtree of $\delta$ in
an optimal transformation forest $G_{\mathbb{S}}(x,y)$ with
$N_{\mathcal{S}(\delta)}(x)~{}=~{}\\{u_{i},\ldots,u_{j}\\}$. Then,
$\operatorname{val}(\delta)=\max(x_{i},\ldots,x_{j})$ for increasing subtrees
and $\operatorname{val}(\delta)=\min(x_{i},\ldots,x_{j})$ for decreasing
subtrees.

Figure 6: Structure of the subtree of $\delta$ explained in the proof of Lemma
6. Note, that this is only a schematic representation and that there may be
further intermediate nodes which are not marked.

###### Proof of Lemma 6.

Without loss of generality, we prove this assumption for increasing subtrees.
Figure 6 depicts this subgraph with all mentioned intermediate nodes. Assume
towards a contradiction, that
$\operatorname{val}(\delta)\neq\max(x_{i},\ldots,x_{j})$. Therefore, there
exists an $u_{\ell}\in\\{u_{i},\ldots,u_{j}\\}$ such that
$\operatorname{val}(\delta)\neq x_{\ell}$. For
$\operatorname{val}(\delta)<x_{\ell}$, it follows that we have a decreasing
edge between $u_{\ell}$ and $\delta$, which is a contradiction. For
$\operatorname{val}(\delta)>x_{\ell}$, let $\alpha$ be the first intermediate
node below $\\{u_{i},\ldots,u_{j}\\}$ such that
$\operatorname{val}(\alpha)\neq\max_{u\in\mathcal{N}_{\mathcal{S}(\alpha)}(x)}(u)$,
where
$\mathcal{N}_{\mathcal{S}(\alpha)}(x)\subseteq\mathcal{N}_{\mathcal{S}(\delta)}(x)$
are the source nodes of the subtree $\mathcal{S}(\alpha)$ of $\alpha$. There
exist two intermediate nodes $\alpha^{\prime}$ and $\alpha^{\prime\prime}$
such that for the source nodes of their subtrees
$\mathcal{S}(\alpha^{\prime})$ and $\mathcal{S}(\alpha^{\prime\prime})$,
respectively, it holds that
$\mathcal{N}_{\mathcal{S}(\alpha^{\prime})}(x)\cup\mathcal{N}_{\mathcal{S}(\alpha^{\prime\prime})}(x)=\mathcal{N}_{\mathcal{S}(\alpha)}(x)$.
It follows that there exists a path from $\alpha^{\prime}$ to $\alpha$ and
from $\alpha^{\prime\prime}$ to $\alpha$. Since $\alpha$ is the first
intermediate node below $\mathcal{N}_{\mathcal{S}(\delta)}(x)$ such that
$\operatorname{val}(\alpha)\neq\max_{u\in\mathcal{N}_{\mathcal{S}(\delta)}(x)}(u)$,
it holds that
$\operatorname{val}(\alpha^{\prime})=\max_{u\in\mathcal{N}_{\mathcal{S}(\alpha^{\prime})}(x)}(u)$
and
$\operatorname{val}(\alpha^{\prime\prime})=\max_{u\in\mathcal{N}_{\mathcal{S}(\alpha^{\prime\prime})}(x)}(u)$.
Consequently, there is an inc-edge on the path from $\alpha^{\prime}$ to
$\alpha$ and on the path from $\alpha^{\prime\prime}$ to $\alpha$. Applying
Lemma 5, this is a contradiction to $G$ being optimal. ∎

In the next lemma, we specify the value of $\delta$ in a subtree
$\mathcal{S}(\delta)$, stating that it is always equal to the value of a
specific source node of $\mathcal{N}_{\mathcal{S}(\delta)}(x)$.

######  Lemma 7.

Let the nodes $\delta_{1}$ and $\delta_{2}$ merge to a node $\delta$ in an
optimal transformation forest $G$. Let $\mathcal{S}(\delta)$ be the subtree of
$\delta$, $\mathcal{S}(\delta_{1})$ be the subtree of $\delta_{1}$ with the
end node $u_{i-1}$, and $\mathcal{S}(\delta_{2})$ be the subtree of
$\delta_{2}$ with the start node $u_{i}$. If the subtree $\mathcal{S}(\delta)$
is increasing (decreasing) and $x_{i-1}>x_{i}$, then
$\operatorname{val}(\delta)=x_{i-1}$ $(\operatorname{val}(\delta)=x_{i})$. If
$x_{i-1}<x_{i}$, then $\operatorname{val}(\delta)=x_{i}$
($\operatorname{val}(\delta)=x_{i-1}$ for decreasing subtrees).

Figure 7: Structure of the subtree of $\delta$ described in the proof of Lemma
7. Note that this is only a schematic representation and that there may be
further intermediate nodes which are not marked.

###### Proof.

Without loss of generality, $\mathcal{S}(\delta)$ is increasing. Figure 7
depicts this subgraph with all mentioned intermediate points. We will only
show the case that $x_{i-1}~{}>~{}x_{i}$ since the other case is analogous. By
Lemma 6, it holds that
$\operatorname{val}(\delta)~{}=~{}\max(\operatorname{val}(\delta_{1}),\operatorname{val}(\delta_{2}))$.
We first show that
$\operatorname{val}(\delta)~{}=~{}\operatorname{val}(\delta_{1})$. Assume
towards a contradiction that
$\operatorname{val}(\delta_{1})<\operatorname{val}(\delta_{2})=\operatorname{val}(\delta)$.
Since $x_{i-1}>x_{i}$, there exists intermediate nodes $\gamma^{\prime}$ and
$\gamma^{\prime\prime}$ on the path between $u_{i}$ and $\delta_{2}$ such that
$x_{i-1}\geq\operatorname{val}(\gamma^{\prime})$ and
$x_{i-1}<\operatorname{val}(\gamma^{\prime\prime})$. Let
$\mathcal{S^{\prime}}(\delta)$ be the modified subtree of
$\mathcal{S}(\delta)$. The only difference between $\mathcal{S}$ and
$\mathcal{S}^{\prime}$ is that $\gamma^{\prime}$ merges to some intermediate
node on the path between $u_{i-1}$ and $\delta_{1}$. The cost of
$\mathcal{S}^{\prime}(\delta)$ is
$\operatorname{Cost}(\mathcal{S}^{\prime}(\delta))~{}=~{}\operatorname{Cost}(\mathcal{S}(\delta))-\operatorname{val}(\gamma^{\prime\prime})-\operatorname{val}(\gamma^{\prime})<\operatorname{Cost}(\mathcal{S}(\delta))$.
This is a contradiction to $G$ being optimal. Applying Lemma 5 and Lemma 6, we
get $\operatorname{val}(\delta)=\operatorname{val}(\delta_{1})$.

In a second step, we prove that
$\operatorname{val}(\delta_{1})=x_{i-1}=\max_{u\in\mathcal{N}_{\mathcal{S}(\delta_{1})}(x)}(\operatorname{val}(u))$.
Assume towards a contradiction, that there exists a $u_{j}\in
N_{\mathcal{S}((\delta_{1})}(x)\setminus u_{i-1}$ such that
$\operatorname{val}(\delta_{1})~{}=~{}x_{j}>x_{i-1}>x_{i}$. Then, it holds
that there exist two intermediate nodes $\delta^{\prime}$ and
$\delta^{\prime\prime}$ on the path between $u_{i-1}$ and $\delta_{1}$ such
that $\operatorname{val}(\delta^{\prime})<\operatorname{val}(\delta_{1})$ and
$\operatorname{val}(\delta^{\prime\prime})~{}=~{}\operatorname{val}(\delta_{1})$.
We consider the modified subtree $\mathcal{S}^{\prime\prime}(\delta)$, which
is almost equal to $\mathcal{S}(\delta)$, the only difference being that
$\delta_{2}$ merges to some intermediate node on the path between
$\delta^{\prime}$ and $\delta^{\prime\prime}$. The cost of
$\mathcal{S}^{\prime\prime}(\delta)$ are
$\operatorname{Cost}(\mathcal{S}^{\prime\prime}(\delta))=\operatorname{Cost}(\mathcal{S}(\delta))-\operatorname{val}(\delta_{1})-\operatorname{val}(\delta_{2})<\operatorname{Cost}(\mathcal{S}(\delta))$.
This is a contradiction to $G$ being optimal. ∎

We will now apply the above properties to the bottleneck nodes in a tree of
Type 4 stating that the first and second bottleneck nodes always have values
of the input time series $x$ and $y$, respectively. Recall, that the first
bottleneck node $\sigma$ is the intermediate node where all source nodes in
the tree of Type 4 merge to, followed by a move edge to the second bottleneck
node $\sigma^{*}$.

######  Corollary 1.

Let $G_{\mathbb{S}}(x,y)$ be an optimal transformation forest. In a tree
$\mathcal{T}$ of Type 4 $\operatorname{val}(\sigma)\in V_{\mathcal{T}}(x)$ and
$\operatorname{val}(\sigma^{*})\in V_{\mathcal{T}}(y)$.

###### Proof.

To prove that $\sigma\in V_{\mathcal{T}}(x)$ we apply Lemma 6 since the upper
part of the tree $\mathcal{T}$ is the subtree of $\sigma$. By symmetry
reasons, it follows that $\sigma^{*}\in V_{\mathcal{T}}(y)$. ∎

###  4.2 The Effect of Perturbing Single Values

We aim to show that there exists a mean of a set of time series that only
consists of points of the input set. To this end, we first make observations
on the effect of shifting points of a time series that are not from $V(X)$. To
this end, we first analyze for two time series $x$ and $y$, how the distance
between $x$ and $y$ may be affected by shifting one point of $x$ by
$\varepsilon\in\mathds{R}$. We let $x_{\varepsilon,i}$ denote the new time
series that is equal to $x$ except at the position $i$, where it has the new
point $x_{i}+\varepsilon$. The change of the node $u_{i}$ in the
transformation forest is denoted by $u_{i}^{\varepsilon}$. In the following we
say that if the distance between $x_{\varepsilon,i}$ and $y$ is shorter than
between $x$ and $y$, the replacement of $x$ by $x_{\varepsilon,i}$ is
_beneficial_. If it leads to a longer distance, it is _detrimental_ , and if
the distance does not change it is _neutral_. Assume that $x_{i}\notin V(y)$,
the next lemma states that if the replacement of $x$ by $x_{\varepsilon,i}$ is
not neutral, it is beneficial for either $\varepsilon$ or $-\varepsilon$.

######  Lemma 8.

Let $x$ and $y$ be two time series with distance $d(x,y)$. If $x_{i-1}\neq
x_{i}\neq x_{i+1}$ and $x_{i}\notin V(y)$, there either exists an
$\varepsilon^{\prime}>0$ such that for all
$\varepsilon\in[0,\varepsilon^{\prime}]$ one of the following equations holds:

(1)

$d(x_{\varepsilon,i},y)+\varepsilon=d(x,y)=d(x_{-\varepsilon,i},y)-\varepsilon$
(beneficial increase),

(2)

$d(x_{-\varepsilon,i},y)+\varepsilon=d(x,y)=d(x_{\varepsilon,i},y)-\varepsilon$
(beneficial decrease),

or there exist $\varepsilon_{I},\varepsilon_{D}>0$ such that

(3.1)

$d(x,y)=d(x_{\varepsilon,i},y)$ for all $\varepsilon\in[0,\varepsilon_{I}]$
(neutral increase), and

(3.2)

$d(x,y)=d(x_{-\varepsilon,i},y)$ for all $\varepsilon\in[0,\varepsilon_{D}]$
(neutral decrease).

Moreover, for beneficial increases
$x_{i}+\varepsilon^{\prime}\in(V(y)\cup\\{x_{i-1},x_{i+1}\\})$, for beneficial
decreases $x_{i}-\varepsilon^{\prime}\in(V(y)\cup\\{x_{i-1},x_{i+1}\\})$, and
for neutral increases and decreases
$x_{i}+\varepsilon_{I},x_{i}-\varepsilon_{D}\in(V(y)\cup\\{x_{i-1},x_{i+1}\\})$.

###### Proof.

We show the lemma for trees of Type 4. All other cases are simpler versions of
this proof. Let $\mathcal{T}$ be a tree of Type 4 in $G_{\mathbb{S}}(x,y)$. By
Lemma 3, the tree $\mathcal{T}$ is monotonic. We assume, without loss of
generality, that all monotonic paths in $\mathcal{T}$ are increasing. We
distinguish whether $u_{i}$ has only predecessors or only successors (Case 1)
or both (Case 2) in $\mathcal{T}$. We denote the predecessors of $u_{i}$ as
$\mathcal{P}$ and the successors of $u_{i}$ as $\mathcal{F}$.

Case 1: $u_{i}$ has only predecessors or successors in $\mathcal{T}$. We prove
the case that $u_{i}$ has only predecessors, the other case is analogous. We
first describe the possible structures of the upper tree in $\mathcal{T}$ for
this case, which are depicted in Figure 8. There is a potential move at
$u_{i}$ to a node $\gamma$. The node $\gamma$ merges to $\delta$ with a node
$\alpha^{*}$, which is the node resulting from a move at $\alpha$. The nodes
$\\{u_{i-\ell},\ldots,u_{i-1}\\}\subseteq\mathcal{P}$ are the source nodes of
the subtree of $\alpha$. Below $\delta$ there may be further subsequent merge
and move operations to the first bottleneck node $\sigma$. Since $x_{i-1}\neq
x_{i}$ there has to be an inc-edge either between $u_{i}$ and $\gamma$, if
$x_{i-1}>x_{i}$, or between $u_{i-1}$ and $\alpha^{*}$, if $x_{i-1}<x_{i}$
because in the first case $\operatorname{val}(\delta)=x_{i-1}$ and in the
second case $\operatorname{val}(\delta)=x_{i}$ (see Lemma 7).

Case 1.1: $x_{i-1}>x_{i}$. There is an inc-edge between $u_{i}$ and $\gamma$
(see Figure 8a). The replacement of $x$ by $x_{\varepsilon,i}$ is a beneficial
increase for all $\varepsilon\in[0,\varepsilon^{\prime}]$ with
$\varepsilon^{\prime}=\operatorname{val}(\gamma)-x_{i}$ because the node
$u_{i}^{\varepsilon}$ approaches the node $\gamma$ and the cost of the adapted
move decrease by $\varepsilon$. Thus, we get the left side of Equation (1),
$d(x_{\varepsilon,i},y)+\varepsilon=d(x,y)$. Since the subtree of $\delta$ is
increasing and $x_{i-1}>x_{i}$, it holds by Lemma 7 that
$\operatorname{val}(\delta)=x_{i-1}$. We get that
$x_{i-1}=\operatorname{val}(\gamma)=x_{i}+\varepsilon^{\prime}$. For the right
side of Equation (1), the argumentation is similar: After replacing $x$ by
$x_{-\varepsilon,i}$ for $\varepsilon\leq\varepsilon^{\prime}$, the cost for
the move between $x_{i}-\varepsilon$ and $\gamma$ are
$\operatorname{val}(\gamma)-x_{i}+\varepsilon$. Therefore, they increase by
$\varepsilon$.

Case 1.2: $x_{i-1}<x_{i}$. There is an inc-edge between $u_{i-1}$ and
$\alpha^{*}$ (see Figure 8b). We modify the structure of $\mathcal{T}$ for the
replacement of $x$ by $x_{\varepsilon,i}$ for
$\varepsilon\in[0,\varepsilon_{I}]$, $\varepsilon_{I}>0$. Let
$\mathcal{T}^{\prime}$ be the modified tree with a new node
$u_{i}^{\varepsilon}$ instead of $u_{i}$. In $\mathcal{T}^{\prime}$, the nodes
$\alpha^{*}$ and $\delta$ does not exist but $\mathcal{T}^{\prime}$ contains a
new node $\delta^{\prime}$ such that
$\operatorname{val}(\delta^{\prime})\in[\operatorname{val}(\alpha^{*}),\operatorname{val}(\sigma^{*})]$.
The node $u_{i}^{\varepsilon}$ merges to $\delta^{\prime}$. The rest of the
tree stays unchanged. For all $\varepsilon\in[0,\varepsilon_{I}]$ with
$\varepsilon_{I}=\operatorname{val}(\sigma^{*})-x_{i}$ the cost of
$\mathcal{T}^{\prime}$ is equal to the cost of $\mathcal{T}$ because we only
shifted a merge operation to another position in the tree (see Figure 8c).
This is a neutral increase for all $\varepsilon\in[0,\varepsilon_{I}]$. It
holds that $x_{i}+\varepsilon_{I}=\sigma^{*}\in V(y)$ (see Corollary 1). Let
$\mathcal{T}^{\prime\prime}$ be another modified tree of $\mathcal{T}$ with a
new node $u_{i}^{-\varepsilon}$ instead of $u_{i}$ for
$\varepsilon\in[0,\varepsilon_{D}]$, $\varepsilon_{D}>0$. The tree
$\mathcal{T}^{\prime\prime}$ does not contain the node $\delta$ but contains a
new node $\delta^{\prime\prime}$ such that
$\operatorname{val}(\delta^{\prime\prime})\in[x_{i-1},\operatorname{val}(\alpha^{*})]$
and $u_{i}^{-\varepsilon}$ merges to $\delta^{\prime\prime}$ (see Figure 8d).
For all $\varepsilon\in[0,\varepsilon_{D}]$ with
$\varepsilon_{D}=\operatorname{val}(\alpha^{*})-x_{i-1}$ we get equal cost of
$\mathcal{T}$ and $\mathcal{T}^{\prime\prime}$ since we only shifted a merge
operation. From Lemma 7 we get that
$\operatorname{val}(\alpha^{*})=\operatorname{val}(\delta)=x_{i}$ and hence
$x_{i}-\varepsilon_{D}=x_{i-1}$.

Figure 8: Schematic representation of the trees discussed for Case 1 in the
proof of Lemma 8. The node $u_{i}$ has only predecessors. The dashed red edges
show potential move operations. a) Case 1.1: $x_{i-1}>x_{i}$. b) Case 2.1:
$x_{i-1}<x_{i}$. c) Proof mechanism introducing the modified tree
$\mathcal{T}^{\prime}$, where the path on which the new node $\delta^{\prime}$
can be shifted on is marked in blue. d) Proof mechanism introducing the
modified tree $\mathcal{T}^{\prime\prime}$ following the same mechanism as in
c).

Case 2: $u_{i}$ has predecessors $\mathcal{P}$ and successors $\mathcal{F}$.
Again, we first describe the upper Type-4-Tree $\mathcal{T}$ (see Figure 9).
Let $\\{u_{i-\ell},\ldots,u_{i-1}\\}\subseteq\mathcal{P}$ be the source nodes
of the subtree of $\alpha$. At $\alpha$ there is a potential move to
$\alpha^{*}$. Let $\\{u_{i+1},\ldots,u_{i+r}\\}\subseteq\mathcal{F}$ be the
source nodes of the subtree of $\zeta$. At $\zeta$ there is a potential move
to $\zeta^{*}$ After a potential move from $u_{i}$ to $\gamma$ there is a
merge with $\alpha^{*}$, which is afterwards merged with $\zeta^{*}$ to an
intermediate node $\delta$. Without loss of generality, we assume this order
of merge to $\delta$. What follows are potential move and merge operations
until all nodes in $N_{\mathcal{T}}(x)$ merge to the first bottleneck node
$\sigma$. Since $\mathcal{T}$ is increasing, the subtree of $\delta$ is
increasing. We further analyze the relation between $x_{i}$ to its direct
predecessor $x_{i-1}$ and its direct successor $x_{i+1}$.

Case 2.1: $x_{i-1}<x_{i}<x_{i+1}$. By Lemma 7, it follows that
$\operatorname{val}(\delta)=x_{i+1}$. Furthermore, there is no inc-edge
between $u_{i}$ and $\gamma$ because $u_{i}$ merges with $\alpha^{*}$ to
$\beta$ with a subsequent inc-edge to $\beta^{*}$ (see Figure 9a). We modify
the tree structure of $\mathcal{T}$ for the replacement of $x$ by
$x_{\varepsilon,i}$. Let $\mathcal{T}^{\prime}$ be the modified tree of
$\mathcal{T}$, where we have the new node $u_{i}^{\varepsilon}$ instead of
$u_{i}$ for $\varepsilon\in[0,\varepsilon_{I}],\varepsilon_{I}>0$. In
$\mathcal{T}^{\prime}$ the node $\beta$ does not exist anymore but
$\mathcal{T}^{\prime}$ includes a new node $\beta^{\prime}$, such that
$\operatorname{val}(\beta^{\prime})\in[\operatorname{val}(\alpha^{*}),\operatorname{val}(\beta^{*})]$,
where $u_{i}^{\varepsilon}$ merges with $\alpha^{*}$. The rest of the tree
stays unchanged. For $\varepsilon\in[0,\varepsilon_{I}]$ with
$\varepsilon_{I}=\operatorname{val}(\beta^{*})-x_{i}$ the cost of
$\mathcal{T}^{\prime}$ is equal to the cost of $\mathcal{T}$ because we only
shifted a merge operation to another position in the tree. This is a neutral
increase for all $\varepsilon\in[0,\varepsilon_{I}]$. It holds that
$x_{i}+\varepsilon_{I}=\operatorname{val}(\beta^{*})=x_{i+1}$. Let further be
$\mathcal{T}^{\prime\prime}$ another modified tree of $\mathcal{T}$. The tree
$\mathcal{T}^{\prime\prime}$ does not contain the node $\beta$, instead it
contains a new node $\beta^{\prime\prime}$, such that
$\operatorname{val}(\beta^{\prime\prime})\in[u_{i-1},\operatorname{val}(\alpha^{*})]$,
where $u_{i}^{-\varepsilon}$ merges to. Again, we only shifted a merge
operation, that leads to equal cost of $\mathcal{T}$ and
$\mathcal{T}^{\prime\prime}$ for all $\varepsilon\in[0,\varepsilon_{D}]$ with
$\varepsilon_{D}=\operatorname{val}(\alpha^{*})-x_{i-1}$. We have
$\operatorname{val}(\alpha^{*})=x_{i}$ and hence
$x_{i}-\varepsilon_{D}=x_{i-1}$.

Case 2.2: $x_{i-1}>x_{i}>x_{i+1}$. This case is analogous to Case 2.1.

Case 2.3: $x_{i-1}<x_{i}>x_{i+1}$. We further assume, without loss of
generality, that $x_{i-1}<x_{i+1}$. By Lemma 7 it holds that
$x_{i}=\operatorname{val}(\delta)$. We have inc-edges between $u_{i-1}$ and
$\alpha^{*}$ and between $u_{i+1}$ and $\zeta^{*}$ (see Figure 9b). The
replacement of $x$ by $x_{-\varepsilon,i}$ for an
$\varepsilon\in[0,\varepsilon_{D}]$ is a beneficial decrease because the merge
points $\beta$ and $\delta$ are shifted by $-\varepsilon$: The move cost are
$\operatorname{val}(\alpha^{*})-\varepsilon-x_{i-1}$ and
$\operatorname{val}(\zeta^{*})-\varepsilon-x_{i+1}$ for the two move
operations, that is a decrease of $2\varepsilon$. The new merge node of
$\beta^{*}$ and $\zeta^{*}$ is denoted by $\delta^{\prime}$. For the new path
between $\delta^{\prime}$ and $\sigma^{*}$ we have cost of
$|\sigma^{*}-\delta^{\prime}+\varepsilon|$, that is an increase of cost by
$\varepsilon$. We get the left side of Equation (2), that is,
$d(x_{-\varepsilon,i},y)+\varepsilon=d(x,y)$ for all
$\varepsilon\in[0,\varepsilon^{\prime}]$ with $\varepsilon_{D}=x_{i}-x_{i+1}$.
It holds that $x_{i}-\varepsilon_{D}=x_{i+1}$. The argumentation of the
detrimental replacement of $x$ by $x_{\varepsilon,i}$ is analogous to Case
1.1.

Case 2.4: $x_{i-1}>x_{i}<x_{i+1}$. There is an inc-edge between $u_{i}$ and
$\gamma$ (see Figure 9c). Again, we further assume, without loss of
generality, that $x_{i-1}<x_{i+1}$. Following the same argumentation as in
Case 1.1, the replacement of $x$ by $x_{\varepsilon,i}$ is a beneficial
increase for all $\varepsilon\in[0,\varepsilon_{I}]$ with
$\varepsilon_{I}=\operatorname{val}(\gamma)-x_{i}$. By Lemma 7, it holds that
$\operatorname{val}(\beta)=x_{i-1}$ and $\operatorname{val}(\delta)=x_{i+1}$.
Note, that there are no increasing paths between $u_{i-1}$ and $\beta^{*}$ and
$u_{i+1}$ and $\zeta^{*}$ because otherwise there is no move between $u_{i}$
and $\gamma$ (see Lemma 5). It holds that
$\operatorname{val}(\gamma)=x_{i-1}=x_{i}+\varepsilon^{\prime}$. The
detrimental replacement of $x$ by $x_{-\varepsilon,i}$ is analogous to Case
1.1. ∎

Figure 9: Schematic representation of the trees discussed for Case 2 in the
proof of Lemma 8. The node $u_{i}$ has predecessors and successors. a) Case
2.1: $x_{i-1}<x_{i}<x_{i+1}$. b) Case 2.3: $x_{i-1}<x_{i}>x_{i+1}$. c) Case
2.4: $x_{i-1}>x_{i}<x_{i+1}$.

Let us briefly discuss the trees of Type 1–3. If the tree $\mathcal{T}$ is of
Type 3, then $\operatorname{val}(\sigma^{*})$ is already in
$\mathcal{N}_{\mathcal{T}}(y)$. The same proof as for trees of Type 4 can be
applied. Since the symmetries properties hold for the MSM metric, the Lemma
holds for trees of Type 2 as well. For a tree containing only a move edge, the
argumentation is the same as in Case 1.1.

In the following, we regard a _block_ $\mathcal{B}$ of adjacent source nodes
$N_{\mathcal{B}}(x)=\\{u_{i},\ldots,u_{\ell}\\}$ representing points of equal
value of a time series $x$. A block is a maximal contiguous sequence of nodes
with the same value. Our aim is to show a generalization of Lemma 8 shifting
all points of a block $\mathcal{B}$ by some $\varepsilon\in\mathds{R}$. We
show that shifting a block is either beneficial for one direction or neutral
for both directions. Let $x_{\varepsilon,i,\ell}$, $i<\ell$, denote the time
series that is equal to $x$ except at the positions $i,\ldots,\ell$, where the
points $x_{i}$ of $x$ are replaced by $x_{i}+\varepsilon$. The definitions of
beneficial, detrimental or neutral replacements of $x$ by
$x_{\varepsilon,i,\ell}$ are analogous to the previous one. A block may be
contained in several trees, hence shifting a block affects the cost of all
these trees. To count the number of trees with beneficial or detrimental
replacement, we introduce two further parameters
$\rho_{I},\rho_{D}\in\mathds{N}$.

######  Lemma 9.

Let $x=(x_{1},\ldots,x_{m})$ and $y=(y_{1},\ldots,y_{n})$ be two time series
with a distance $d(x,y)$. If we consider a block $\mathcal{B}$ of similar
points $N_{\mathcal{B}}(x)=\\{u_{i},\ldots,u_{\ell}\\}$ with $x_{i}\notin
V(y)$, then there either exists an $\varepsilon^{\prime}>0$ and
$\rho_{I},\rho_{D}\in\mathds{N}$ such that for all
$\varepsilon\in[0,\varepsilon^{\prime}]$ one of the following equations holds:

(1)

$d(x_{\varepsilon,i,\ell},y)+\rho_{I}\cdot\varepsilon=d(x,y)=d(x_{-\varepsilon,i,\ell},y)-\rho_{D}\cdot\varepsilon$
(b. increase),

(2)

$d(x_{-\varepsilon,i,\ell},y)+\rho_{D}\cdot\varepsilon=d(x,y)=d(x_{\varepsilon,i,\ell},y)-\rho_{I}\cdot\varepsilon$
(b. decrease),

or there exist $\varepsilon_{I},\varepsilon_{D}>0$ such that

(3.1)

$d(x,y)=d(x_{\varepsilon,i},y)$ for all $\varepsilon\in[0,\varepsilon_{I}]$
(neutral increase), and

(3.2)

$d(x,y)=d(x_{-\varepsilon,i},y)$ for all $\varepsilon\in[0,\varepsilon_{D}]$
(neutral decrease).

Moreover, for beneficial increases
$x_{i}+\varepsilon^{\prime}\in(V(y)\cup\\{x_{i-1},x_{i+1}\\})$, for beneficial
decreases $x_{i}-\varepsilon^{\prime}\in(V(y)\cup\\{x_{i-1},x_{i+1}\\})$, and
for neutral increases and decreases
$x_{i}+\varepsilon_{I},x_{i}-\varepsilon_{D}\in(V(y)\cup\\{x_{i-1},x_{i+1}\\})$.

Figure 10: Schematic representation of the three cases for proving Lemma 9,
depending on the structure of a block $\mathcal{B}$. a) Case 1.1:
$N_{\mathcal{T}}(x)=N_{\mathcal{B}}(x)$. b) Case 1.2:
$|N_{\mathcal{T}}(x)|>|N_{\mathcal{B}}(x)|$. c) Case 2: The nodes in
$N_{\mathcal{B}}(x)$ belong to different trees.

###### Proof.

We distinguish whether all nodes of a block $\mathcal{B}$ belong to the same
tree or if they are in different trees. Without loss of generality, we specify
monotonic paths and trees to be increasing.
Case 1: All nodes $N_{\mathcal{B}}(x)$ are in one tree $\mathcal{T}$ (see
Figure 10a,b). Without loss of generality, $\mathcal{T}$ is considered to be a
tree of Type 4, since all other cases follows the same or a simpler
argumentation. We further distinguish whether the nodes of
$N_{\mathcal{B}}(x)$ are the only nodes in $\mathcal{T}$.
Case 1.1: $N_{\mathcal{T}}(x)=N_{\mathcal{B}}(x)$. For the bottleneck nodes it
holds that $\operatorname{val}(\sigma)=x_{i}$ and
$\operatorname{val}(\sigma^{*})\in V(y)$ (see Corollary 1). The replacement of
$x$ by $x_{\varepsilon,i,\ell}$ is a beneficial increase for all
$\varepsilon\in[0,\varepsilon^{\prime}]$ with
$\varepsilon^{\prime}=\sigma^{*}-x_{i}$ because the intermediate node is also
shifted to $\sigma+\varepsilon$ that leads to lower move cost of
$\operatorname{val}(\sigma^{*})-\operatorname{val}(\sigma)-\varepsilon$, that
is, a decrease by $\varepsilon$. Therefore, we get the left side of the first
equation $d(x_{\varepsilon,i,\ell},y)+\varepsilon=d(x,y)$ for $\rho_{I}=1$. It
holds that $x_{i}+\varepsilon^{\prime}=\operatorname{val}(\sigma^{*})\in
V(y)$. For the right side of the equation with $\rho_{D}=1$, the argumentation
is similar. Replacing $x$ by $x_{-\varepsilon,i,\ell}$ we get new move cost of
$\operatorname{val}(\sigma^{*})-\operatorname{val}(\sigma)+\varepsilon$, that
is, an increase by $\varepsilon$.

Case 1.2: $|N_{\mathcal{T}}(x)|>|N_{\mathcal{B}}(x)|$. Since $\mathcal{T}$ is
a tree of Type 4, all nodes in $N_{\mathcal{T}}(x)$ merge to the intermediate
node $\sigma$. Moreover, it is evident that the merge of adjacent points in
$\mathcal{T}$ that are equal creates lower cost than merging two points that
are different. Therefore, there exists an intermediate node $\sigma^{\prime}$
where all nodes in $N_{\mathcal{B}}(x)$ merge to (see Figure 10b). Then Lemma
8 can be applied for $u_{i}=\sigma^{\prime}$ with $\rho_{I}=\rho_{D}=1$.
Depending on the case, an $\varepsilon_{I}$ is specified such that we get one
of the above equations for an $\varepsilon\in[0,\varepsilon_{I}]$. For
$\varepsilon=\varepsilon_{I}$, the block is shifted until it reaches a value
of the adjacent points of the block, that is $x_{i-1}$ or $x_{\ell+1}$, or it
reaches a point in $V(y)$.

Case 2: The nodes in $N_{\mathcal{B}}(x)$ belong to different trees (see
Figure 10c). In this case, we need to count how many trees we have beneficial
increases and decreases. To decide whether a replacement is beneficial or
detrimental, there are two possible cases of trees belonging to the block
$\mathcal{B}$. The first case is that all nodes in a tree in $\mathcal{B}$
belong to $N_{\mathcal{B}}(x)$. Then we can apply Case 1.1. The second case
concerns the boundary values of $N_{\mathcal{B}}(x)$ merging with the
predecessors or successors of the block $\mathcal{B}$. Following the
argumentation of Case 1.2, we determine if the replacement of $x$ by
$x_{\varepsilon,i,\ell}$ is beneficial, neutral, or detrimental. Ignoring
neutral replacements, we set $x_{i,\ell}^{+}$ as the number of trees for which
we have a beneficial increase and $x_{i,\ell}^{-}$ as the number of trees for
which we have a beneficial decrease. Shifting a whole block may therefore lead
to a reduction of distance of more than $\varepsilon$. We get the above
statement for $\rho_{I}=x_{i,\ell}^{+}$ and $\rho_{D}=x_{i,\ell}^{-}$. By
Lemma 8, we get an $\varepsilon_{\mathcal{T}}$ for all trees $\mathcal{T}$ in
a block $\mathcal{B}$ restricting a beneficial or neutral replacement. Let
$\varepsilon^{+}_{min}$ be the minimum of all $\varepsilon_{\mathcal{T}}$ for
which we have a beneficial increase. Analogously, $\varepsilon^{-}_{min}$ is
defined for beneficial decreases. Without loss of generality, we assume
$x_{i,\ell}^{+}>x_{i,\ell}^{-}$. Hence, it holds that for
$x_{i}+\varepsilon^{+}_{min}$ is in $\\{x_{i-1},x_{\ell+1}\\}$ or in $V(y)$. ∎

###  4.3 MSM-Mean Values

We now use beneficial and neutral replacements to prove that for any set $X$
there exists a mean $m$ such that all points of $m$ are points of at least one
time series of $X$.

######  Lemma 10.

Let $X=\\{x^{(1)},\ldots,x^{(k)}\\}$ be a set of $k$ time series. Then there
exists a mean $m~{}=~{}(m_{1},\ldots,m_{N})$ of $X$ such that $m_{i}\in V(X)$
for all $m_{i},i\in[N]$.

###### Proof.

Assume towards a contradiction that every mean has at least one point that is
not in $V(X)$. Among all means, choose a mean $m$ such that 1) $n_{V}$, the
number of points of $m$ that are in $V(X)$, is maximum and 2) among all means
with $n_{V}$ points from $V(X)$, the number of transitions from $m^{(i)}_{j}$
to $m^{(i)}_{j+1}$ where $m^{(i)}_{j}\neq m^{(i)}_{j+1}$ is minimum. In other
words, $m$ has a minimal number of blocks. Let $\mathcal{B}$ be a block in $m$
whose points are not in $V(X)$. We apply Lemma 9 to show that there exists an
$\varepsilon\in\mathds{R}$ such that $m_{\varepsilon,i,\ell}$ is a mean where
the points of the shifted block $\mathcal{B}$ reach a point of a predecessor
or successor of $\mathcal{B}$ or a point in $V(X)$. We now specify
$\varepsilon$. First, we determine whether $\varepsilon$ is positive or
negative. For each sequence, one of the Cases (1) to (3) of Lemma 9 applies.
For each time series in $X$, we introduce two variables to count how many
beneficial increases and decreases we have. Neutral replacements are not
counted. Let $x^{+}$ be the sum of $\rho_{I}$ for beneficial increases and
$x^{-}$ be the sum of $\rho_{D}$ for beneficial decreases of all time series.
If $x^{+}\geq x^{-}$, we set $\varepsilon$ as the minimum of the specified
$\varepsilon^{\prime}$ for beneficial increases and all $\varepsilon_{I}$ (see
Lemma 9). If $x^{+}<x^{-}$ we set $\varepsilon$ as the maximum of the
specified $-\varepsilon^{\prime}$ for beneficial decreases and all
$-\varepsilon_{D}$. Compared to the mean $m$, all values of
$m_{\varepsilon,i,\ell}$ are the same except the values of the shifted block.
By Lemma 9 the points of the new mean $m_{\varepsilon,i,\ell}$ are shifted for
the specified $\varepsilon$ until they reach a point of the right or left
neighbor block or a point in $V(X)$. If they reach a point of the right or
left neighbor block, we have a contradiction to the selection of a mean with a
minimal number of transitions. If they reach a point in $V(X)$, we have the
contradiction to the selection of a mean with minimal number of values that
are not in $V(X)$. ∎

##  5 Computing an exact MSM-Mean

Based on Lemma 10, we now give a dynamic program computing a mean $m$ of $k$
time series $X=\\{x^{(1)},\ldots,x^{(k)}\\}$. The transformation operations
are described for the direction transforming $X$ to $m$.

###  5.1 Dynamic Program

We fill a $(k+2)$-dimensional table $D$ with entries
$D[(p_{1},\ldots,p_{k}),\ell,s]$, where

  * •

$p_{i}\in[n_{i}]$ indicates the _current position_ in time series $x^{(i)}$,

  * •

the index $\ell\in[N]$ indicates the _current position of $m$_, and

  * •

$s$ is the index of a point $v_{s}\in V(X)$.

We also say that $(p_{1},\ldots,p_{k})$ are the _current positions of $X$_.
For clarity, we write $p=(p_{1},\ldots,p_{k})$. The entry $D[p,\ell,s]$
represents the cost of the partial time series
$\\{(x_{1}^{(1)},\ldots,x_{p_{1}}^{(1)}),\ldots,(x_{1}^{(k)},\ldots,x_{p_{k}}^{(k)})\\}$
transforming to a mean $(m_{1},\ldots,m_{\ell})$ assuming that
$m_{\ell}=v_{s}$. Giving a recursive formula filling table $D$ we have two
transformation cases. The case distinction is based on the computation of the
MSM distance for two time series $x=(x_{1},\ldots,x_{m})$ and
$(y_{1},\ldots,y_{n})$. This computation fills a two-dimensional table
$D^{*}$. An entry $D^{*}[i,j]$ represents the cost of transforming the partial
time series $(x_{1},\ldots,x_{i})$ to the partial time series
$(y_{1},\ldots,y_{j})$. The distance $d(x,y)$ is given by $D^{*}[m,n]$. Stefan
et al. [19] give the recursive formulation of the MSM metric as the minimum of
the cost for the three transformation operations.

$\displaystyle D^{*}[i,j]$
$\displaystyle=\min\\{A_{MO}[i,j],A_{M}[i,j],A_{SP}[i,j]\\},\text{where}$
$\displaystyle A_{MO}[i,j]$ $\displaystyle=D^{*}[i-1,j-1]+|x_{i}-y_{i}|$
$\displaystyle(move)$ $\displaystyle A_{M}[i,j]$
$\displaystyle=D^{*}[i-1,j]+C(x_{i},x_{i-1},y_{j})$ $\displaystyle(merge)$
$\displaystyle A_{SP}[i,j]$
$\displaystyle=D^{*}[i,j-1]+C(y_{j},x_{i},y_{j-1})$ $\displaystyle(split)$

for

$C(x_{i},x_{i-1},y_{j})=\begin{cases}c\;\;\;\;\text{if }x_{i-1}\leq x_{i}\leq
y_{j}\text{ or }x_{i-1}\geq x_{i}\geq y_{j}&\\\
c+\min(|x_{i}-x_{i-1}|,|x_{i}-y_{j}|)\quad\text{otherwise}.&\end{cases}$

When the recursion reaches a border of $D^{*}$, we have the special cases
$D^{*}[i,1]=D^{*}[i-1,1]+C(x_{i},x_{i-1},y_{1})$ (only merge operation may be
further applied) and $D^{*}[1,j]=D^{*}[1,j-1]+C(y_{j},x_{1},y_{j-1})$ (only
split operation may be further applied). The base case is reached for
$D^{*}[1,1]=|x_{1}-y_{1}|$ where only a move operation is applied.

For the recursion formula for the MSM-Mean problem, we distinguish between
applying moves and splits ($A_{MS}$) and only merges ($A_{ME}$):

$\displaystyle D[p,\ell,s]=\min\\{A_{MS}[p,\ell,s],A_{ME}[p,\ell,s]\\}.$

To distinguish between these cases, we introduce index sets $I_{MO},I_{SP}$,
and $I_{ME}$ for move, split, and merge operations, respectively. They
represent the indices for those time series which either move, split, or
merge. All index sets are subsets of $I=[k]$. Let $\overline{p}_{MO}$ be the
tuple of $p$ where $\overline{p}_{i}=p_{i}-1$ for all $i\in I_{MO}$. The tuple
$\overline{p}_{ME}$ is defined analogously. The first case considers that at
some current positions of $X$ there are move and at all other positions there
are split operations. It holds that $I_{MO}\cup I_{SP}=I$. For these
operations, the recursive call of the function decreases the current position
of $m$:

$\displaystyle A_{MS}[p,\ell,s]=$ $\displaystyle\min_{v_{s^{\prime}}\in
V(X)}\\{\min_{I_{MO},I_{SP}}\bigl{(}D[\overline{p}_{MO},\ell-1,s^{\prime}]$
$\displaystyle+\sum_{i\in I_{MO}}|x_{p_{i}}^{(i)}-v_{s}|+\sum_{i\in
I_{SP}}C(v_{s},x_{p_{i}}^{(i)},v_{s^{\prime}})\bigr{)}\\}.$

The second case treats merge operations of at least one current position of
$X$. If a merge is applied, all other time series pause since the recursive
call does not decrease the position of $m$:

$\displaystyle A_{ME}[p,\ell,s]=$
$\displaystyle\min_{I_{ME}}\bigl{(}D[\overline{p}_{ME},\ell,s]+\sum_{i\in
I_{ME}}C(x_{p_{i}}^{(i)},x_{p_{i}-1}^{(i)},v_{s})\\}.$

For the last step in the recursion, the entries $D[(1,\ldots,1),1,s]$ for all
$v_{s}\in V(X)$ are calculated by

$\displaystyle D[(1,\ldots,1),1,s]=\sum_{i\in I}|x_{1}^{(i)}-v_{s}|.$

All entries $D[p,\ell,s]$ for which $p_{i}<1$ for some $i\in[k]$ is set to
$+\infty$. If $\ell=1$ and all $p_{i}>1$, only merge operations may be
applied:

$\displaystyle D[p,1,s]=\min_{I_{ME}\subseteq
I}\bigl{(}D[\overline{p}_{ME},1,s]+\sum_{i\in
I_{ME}}C(x_{p_{i}}^{(i)},x_{\overline{p}_{i}}^{(i)},v_{s}).$

The correctness of the dynamic program hinges on the fact that in the
recursive definition of the pairwise distance, the value of $D^{*}[i,j]$
depends only on the values of $D^{*}[i,j-1]$, $D^{*}[i-1,j]$,
$x_{i},y_{j},x_{i-1}$, and $y_{j-1}$; we omit the formal correctness proof.

###  5.2 Running Time Bound

We now show an upper bound on the maximum mean length in terms of the total
length of $X$. To this end, we first make the observation that the index set
$I_{MO}$ is never empty. That is, it is not optimal to apply only split
operations in one recursion step.

######  Lemma 11.

Let $m$ be a mean of a set of $k$ time series $X$. It holds that
$D[p,\ell,s]<\min_{v_{s^{\prime}}\in V(X)}\\{D[p,\ell-1,s^{\prime}]+\sum_{i\in
I}C(v_{s},x_{p_{i}}^{(i)},v_{s^{\prime}})\\}$.

###### Proof.

Let $D(X,m)$ be the distance of a mean $m$ to $X$. Assume towards a
contradiction, that there exists a recursion step, where $I_{MO}=\emptyset$.
That is, in each time series in $X$ there is a split at a point
$x_{p_{i}}^{(i)},i\in I$ to the points $m_{\ell}$ and $m_{\ell-1}$. We regard
the cost for the transformation up to the positions $(p_{1},\ldots,p_{k})$ of
$X$ and $\ell$ of $m$. Applying the recursion formula for $I_{SP}=I$, we get
$D[p,\ell,s]=\min_{v_{s^{\prime}}\in V(X)}\\{D[p,\ell-1,s^{\prime}]+\sum_{i\in
I}C(v_{s},x_{p_{i}}^{(i)},v_{s^{\prime}})\\}.$ Let $m^{\prime}$ be a mean of
$X$ equal to $m$ but where $m_{\ell}$ is deleted. For the mean $m^{\prime}$,
we save the cost for splitting $\sum_{i\in
I}C(v_{s},x_{p_{i}}^{(i)},v_{s^{\prime}})$, without changing the alignment of
all other points in $X$. It follows that $D(X,m^{\prime})<D(X,m)$. This is a
contradiction to $m$ being a mean. ∎

Lemma 11 now leads to the following upper bound for the MSM-Mean length.

######  Lemma 12.

Let $X=\\{x^{(1)},\ldots,x^{(k)}\\}$ be a set of time series with maximum
length $max_{j\in[k]}|x^{(j)}|=n$. Then, every mean $m$ has length at most
$(n-1)k+1$.

###### Proof.

Towards a contradiction, let $m$ be a mean of $X$ with length $N>(n-1)k+1$.
The entry of the first recursion call is $D[(n_{1},\ldots,n_{k}),N,s]$.
Consider any sequence of recursion steps from $D[(n_{1},\ldots,n_{k}),N,s]$ to
$D[(1,\ldots,1),\cdot,\cdot]$; each step is associated with index sets
$I_{MO}$ and $I_{SP}$, or $I_{ME}$. By Lemma 11, it holds that
$I_{MO}~{}\neq~{}\emptyset$ in each step. That is, at least one current
position of $X$ is reduced by one in each recursion step until the entry
$D[(1,\ldots,1),\ell^{\prime},s^{\prime}]$ is reached. These are at most
$(n-1)k+1$ recursion steps. Since $N~{}>~{}(n-1)k+1$, it holds that
$\ell^{\prime}>1$. The only possibility for a further recursion step for
$D[(1,\ldots,1),\ell^{\prime},s^{\prime}]$ is to set $I_{SP}=I$, since
$D[p,\ell,s]=+\infty$ whenever $p_{i}<1$ for some $i$. By Lemma 11, we get a
contradiction to $m$ being a mean. ∎

We now bound the running time of our algorithm.

######  Lemma 13.

The MSM-Mean problem for $k$ input time series of length at most $n$ can be
solved in time $\mathcal{O}(n^{k+3}2^{k}k^{3})$.

###### Proof.

In the dynamic programming table $D$ at most $n^{k+2}k^{2}$ entries have to be
computed. This number is the dimension of $k$ time series with maximum length
$n$, the maximum length of the mean $(n-1)k+1\leq kn$ and the size of $V(X)$
which is at most $kn$. For each table entry, the minimum over the set $V(X)$
is taken, which includes again $kn$ data points. For each minimum over $V(X)$
all subsets of $[k]$ are considered which are at most $2^{k}$ sets. All
subsets of $[k]$ are only generated once for both $I_{MO}$ and $I_{ME}$. Thus,
filling the table iteratively takes time $\mathcal{O}(n^{k+3}2^{k}k^{3})$.

For the traceback, the start entry of $D$ is any of the position
$(n_{1},\ldots,n_{k})$ with minimal cost, that is,

$D[(n_{1},\ldots,n_{k}),\ell_{start},s_{start}]=\min_{\ell,s}D[(n_{1},\ldots,n_{k}),\ell,s].$

The length of the mean $m$ is $\ell_{start}$ with $m_{start}=v_{s_{start}}$.
In each traceback step, the _predecessors_ of the current entry are
determined, that are the entries leading to the cost of the current entry. A
predecessor of an entry is not unique. For setting the mean data point we
consider the current entry $D[(p_{1},\ldots,p_{k}),\ell,s]$ and the entry of
the predecessor $D[(q_{1},\ldots,q_{k}),\ell^{\prime},s^{\prime}]$. If
$\ell^{\prime}=\ell-1$, the point $v_{s^{\prime}}$ is assigned to the mean
point $m_{\ell^{\prime}}$ and we continue with the next traceback step.
Otherwise, the next traceback step is directly applied without assigning a
mean point. We repeat this procedure until we reach the entry
$D[(1,\ldots,1),1,s^{*}]$. The running time of filling the table clearly
dominates the linear time for the traceback. ∎

###  5.3 Implementation & Window Heuristic

We fill the table $D$ iteratively and apply the above described traceback
mechanism afterwards. Since the running time of MSM-Mean will often be too
high for moderate problem sizes, we introduce the _window heuristic_ to avoid
computing all entries of table $D$. Similar to a heuristic of Levenshtein
distance [7], the key idea is to introduce a parameter $d$ called the window
size representing the maximum difference between the current positions of the
time series within the recursion. All entries whose current positions are not
within distance $d$ will be discarded. For example, an entry with current
position $(6,3,4)$ of $X$ will not be computed for $d=2$. In the case of a set
of time series with unequal lengths, where $n_{min}$ and $n_{max}$ denotes the
minimum length and the maximum lengths, respectively, of all time series, $d$
has to be greater than $n_{max}-n_{min}$.

##  6 Experimental Evaluation

This section provides important results from a selection of experiments using
implementations of mean algorithms222All code is available on GitHub:
https://github.com/JanaHolznigenkemper/msm_mean. After a description of the
experimental setup, we first provide a running time comparison of the DTW-Mean
algorithm [31] and our MSM-Mean algorithm. Furthermore, we examine accuracy
and running times of MSM-Mean for various heuristics.

###  6.1 Experimental Setup

The running times of our Java implementations are measured on a server with
Ubuntu Linux 20.04 LTS, two AMD EPYC 7742 CPUs at 2.25 Ghz (2.8 Ghz boost),
1TB of RAM, Java version 15.0.2. Our implementations are single-threaded. For
our results at most 26GB of RAM were occupied.

The experiments are conducted on 20 UCR data sets [21] that Stefan et al. [19]
already used (see Table 1). The UCR data sets were collected for the use of
time series classification. Each set consists of a training and a testing set.
The data sets consists of time series of different classes and different
lengths. Since we are not using the sets for classification use cases yet, we
just take the training sets of each data set for our experimental setup. The
parameter $c$ is set constant for every data set following the suggestions of
Stefan et al. [19].

Table 1: List of 21 UCR time series data sets. For our running time experiment, we did not take the Italy Power Demand data set (*) since the time series are too short. The quality analysis of MSM-Mean using this data set was conducted for $c\in\\{0.01,0.1,0.2,0.5\\}$.  Data Set | #Classes | #TS Training | TS Length |  MSM $c$
---|---|---|---|---
50words | 50 | 450 | 270 | 1
Adiac | 37 | 390 | 176 | 1
Beef | 5 | 30 | 470 | 0.1
CBF | 3 | 30 | 128 | 0.1
Coffee | 2 | 28 | 286 | 0.01
ECG | 2 | 100 | 96 | 1
FaceAll | 14 | 560 | 131 | 1
Face (four) | 4 | 24 | 350 | 1
Fish | 7 | 175 | 463 | 0.1
Gun Point | 2 | 50 | 150 | 0.01
Italy Power* | 2 | 67 | 24 | *
Lightning-2 | 2 | 60 | 367 | 0.01
Lightning-7 | 7 | 70 | 319 | 1
OliveOil | 4 | 30 | 470 | 0.01
OSU Leaf | 6 | 200 | 427 | 0.1
Swedish Leaf | 15 | 500 | 128 | 1
Synthetic C. | 6 | 300 | 60 | 0.1
Trace | 4 | 100 | 275 | 0.01
Two Pattern | 4 | 1000 | 128 | 1
Wafer | 2 | 1000 | 152 | 1
Yoga | 2 | 300 | 426 | 0.1

Due to the complexity of the algorithms, we draw time series samples from the
training sets obtained from the UCR archive in the following way. For each
class of the training sets, we randomly pick $k$ time series,
$k\in\\{3,4,5\\}$, and for each of them, we cut out a contiguous subsequence
of length $n$ starting at a random data point, $n\in\\{10,\ldots,50\\}$. In
addition, we limit the length of the mean time series to at most $n$.

###  6.2 Running Time Comparisons

In our first experiment, we consider the running times for $k=3,4$. Figure 11
shows the average running time over all 20 data sets as a function of $n$. Our
MSM-Mean algorithm is substantially faster than the DTW counterpart. The
outlier in the DTW graph is due to a data set where the implementation does
not complete within 10 minutes. Figure 12 in the appendix provides box plots
depicting the running times of both algorithms for $k=4$ and $n=10\ldots,13$.
They reveal that the MSM-Mean algorithm has smaller medians and interquartile
ranges and fewer outliers of high running times compared to the DTW-Mean
algorithm. The MSM-Mean implementation was able to compute any instance for
$k=3$, $n<43$, $k=4$, $n<19$, and $k=5$, $n<11$ within 10 minutes. For DTW-
Mean, this was only the case for $k=3$, $n<29$ and $k=4$, $n<14$.

Figure 11: Running time comparison of MSM-Mean and DTW-mean for $k=3$ as a
function of $n$ Figure 12: Running time comparison of MSM-Mean and DTW-mean
for $k=4$

####  6.2.1 MSM-Mean Quality

To evaluate the quality of the MSM-Mean, we use the algorithm on the
ItalyPowerDemand data set [21] where each time series has length 24. The data
set contains two classes. For different values of
$c\in\\{0.01,0.1,0.2,0.5\\}$, Table 2 shows the distance of MSM-Mean to three
other time series. The first row reports the distance when the time series
belong to one class, while the second row provides the distance when taking
them from both classes. The results confirm for all $c$ that distances of MSM-
Mean are lower when time series belong to one class.

Table 2: Distance of the mean to time series of the data set ItalyPowerDemand of one class and to time series of mixed classes for k=3 and n=24 for varying $c$ c | 0.01 | 0.1 | 0.2 | 0.5
---|---|---|---|---
one class | 5.55 | 7.05 | 8.02 | 9.72
two classes | 11.66 | 15.41 | 18.46 | 26.1

####  6.2.2 Length of the Mean

We implemented two versions of the MSM-Mean algorithm, one with a fixed length
$n$ of the mean and one without length constraints. As shown in Lemma 12, the
lengths of MSM-Mean is at most $(n-1)k+1$. However, the results of our
experiments for $k=3$ and $n\in\\{10,\ldots,30\\}$ show that the length of
MSM-Mean is always exactly $n$. Thus, it is advisable to use this constraint
as done in the experiments discussed above.

###  6.3 MSM-Mean Heuristics

####  6.3.1 Discretization Heuristic

Because the domain size of the values of a time series has an significant
effect on the performance of MSM-Mean algorithm, we propose a second heuristic
where the domain is split into $v$ buckets of equal length. Each value $x$ of
a time series is then replaced by the center point of the bucket to which $x$
belongs. Thus, there are at most $v$ different values in total.

Figure 13 shows the running time of this heuristic as a function of $v$ for
$k=3$ and $n=30$. There is a substantial (close to linear) decrease in the
running time with a decreasing number of buckets. Moreover, the relative error
is quite moderate: We observed an average and maximum error of 4.6% and 8.47%,
respectively.

Figure 13: Running time for MSM-Mean calculation of $k=3$ and $n=30$ regarding
the discretization heuristic.

####  6.3.2 Window Heuristic

In the following, we investigate the window heuristic described in Section 5.3
for the MSM-Mean problem and $k=3$, $n\in\\{10,\ldots,42\\}$. We examine the
window size $d=1,2,3$ in our experiments. We analyze relative error of the
exact mean and the means obtained from the window heuristic. As expected, the
higher the window size $d$ the smaller is the relative error. The relative
error averaged over all $n$ and all data sets was $4.8\%,3.2\%,2.4\%$ and the
maximum relative error was $9.1\%,6.4\%,5.4\%$ for $d=1,2,3$, respectively.
Figure 14 shows the running time of the window heuristic in comparison to the
exact computation as a function of $n$. Note that the y-axis plots the running
time on a logarithmic scale. For all parameter settings, the running times
improve substantially in comparison to the exact approach.

Figure 14: Average running time of computing the exact mean and mean using the
window heuristic for $d=1,2,3$ for $k=3$ and $n\in\\{10,\ldots,42\\}$.

##  7 Conclusion and Future Work

This paper introduces the MSM-Mean problem of computing the mean of a set of
time series for the Move-Split-Merge (MSM) metric. We present an exact
algorithm for MSM-Mean with a better running time than a recent algorithm for
computing the mean for the DTW distance. Experimental results confirm the
theoretically proven superiority of our MSM-Mean algorithm in comparison to
the DTW counterpart. The key observation of our method is that an MSM-Mean
exists whose data points occur in at least one of the underlying time series.
In addition, we provide an an upper bound for the length of MSM-Mean. In our
experiments, the maximum mean length is much shorter, rarely exceeding the
length of the longest time series. The paper also provides two heuristics for
speeding up the computation of the mean without sacrificing much accuracy, as
shown in our experimental evaluation.

In future work we will tackle the following issues. First, we will examine how
to use MSM-Mean in real clustering and classification problems. Second, we
plan to develop optimization strategies such as the _A*-Algorithm_ [4] for
further improving the running time of our algorithm to avoid filling up the
entire dynamic programming table. As a starting point, the structure of the
transformation forests and the metric properties of the MSM distance could be
further explored. Third, the metric properties, especially the triangle
inequality, of the MSM distance enables applications of the MSM-Mean to metric
indexing. Finally, we conjecture MSM-Mean to be NP-hard. Proving this
conjecture could be a next research step.

## Declarations

The authors have no relevant financial or non-financial interests to disclose.

## References

  * [1] Maurice Fréchet “Les éléments aléatoires de nature quelconque dans un espace distancié” In _Annales de l’institut Henri Poincaré_ 10.4, 1948, pp. 215–310
  * [2] Vladimir I Levenshtein “Binary codes capable of correcting deletions, insertions, and reversals” In _Soviet physics doklady_ 10.8, 1966, pp. 707–710 Soviet Union
  * [3] James MacQueen “Some methods for classification and analysis of multivariate observations” In _Proceedings of the fifth Berkeley symposium on mathematical statistics and probability_ 1.14, 1967, pp. 281–297 Oakland, CA, USA
  * [4] Peter E Hart, Nils J Nilsson and Bertram Raphael “A formal basis for the heuristic determination of minimum cost paths” In _IEEE transactions on Systems Science and Cybernetics_ 4.2 IEEE, 1968, pp. 100–107
  * [5] Hiroaki Sakoe and Seibi Chiba “Dynamic programming algorithm optimization for spoken word recognition” In _IEEE transactions on acoustics, speech, and signal processing_ 26.1 IEEE, 1978, pp. 43–49
  * [6] Joseph P Kruskal “Time warps, string edits, and macromolecules: the theory and practice of sequence comparison” Addison-Wesley, 1983
  * [7] Esko Ukkonen “Algorithms for approximate string matching” In _Information and control_ 64.1-3 Elsevier, 1985, pp. 100–118
  * [8] Donald J Berndt and James Clifford “Using dynamic time warping to find patterns in time series.” In _KDD workshop_ 10.16, 1994, pp. 359–370 Seattle, WA, USA:
  * [9] Gautam Das et al. “Rule Discovery from Time Series.” In _KDD_ 98.1, 1998, pp. 16–22
  * [10] John Aach and George M Church “Aligning gene expression time series with time warping algorithms” In _Bioinformatics_ 17.6 Oxford University Press, 2001, pp. 495–508
  * [11] T Warren Liao “Clustering of time series data—a survey” In _Pattern recognition_ 38.11 Elsevier, 2005, pp. 1857–1874
  * [12] Yasushi Sakurai, Masatoshi Yoshikawa and Christos Faloutsos “FTW: fast similarity search under the time warping distance” In _Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , 2005, pp. 326–337
  * [13] Vit Niennattrakul and Chotirat Ann Ratanamahatana “On clustering multimedia time series data using k-means and dynamic time warping” In _2007 International Conference on Multimedia and Ubiquitous Engineering (MUE’07)_ , 2007, pp. 733–738 IEEE
  * [14] Ville Hautamaki, Pekka Nykanen and Pasi Franti “Time-series clustering by approximate prototypes” In _2008 19th International conference on pattern recognition_ , 2008, pp. 1–4 IEEE
  * [15] David Novak, Michal Batko and Pavel Zezula “Metric index: An efficient and scalable solution for precise and approximate similarity search” In _Information Systems_ 36.4 Elsevier, 2011, pp. 721–733
  * [16] François Petitjean, Alain Ketterlin and Pierre Gançarski “A global averaging method for dynamic time warping, with applications to clustering” In _Pattern recognition_ 44.3 Elsevier, 2011, pp. 678–693
  * [17] François Petitjean and Pierre Gançarski “Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment” In _Theoretical Computer Science_ 414.1 Elsevier, 2012, pp. 76–91
  * [18] Sangeeta Rani and Geeta Sikka “Recent techniques of clustering of time series data: a survey” In _International Journal of Computer Applications_ 52.15 Citeseer, 2012
  * [19] Alexandra Stefan, Vassilis Athitsos and Gautam Das “The move-split-merge metric for time series” In _IEEE transactions on Knowledge and Data Engineering_ 25.6 IEEE, 2012, pp. 1425–1438
  * [20] Saeed Aghabozorgi, Ali Seyed Shirkhorshidi and Teh Ying Wah “Time-series clustering–a decade review” In _Information Systems_ 53 Elsevier, 2015, pp. 16–38
  * [21] Yanping Chen et al. “The UCR Time Series Classification Archive” www.cs.ucr.edu/~eamonn/time_series_data/, 2015
  * [22] Jason Lines and Anthony Bagnall “Time series classification with ensembles of elastic distance measures” In _Data Mining and Knowledge Discovery_ 29.3 Springer, 2015, pp. 565–592
  * [23] François Petitjean et al. “Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm” In _Knowledge and Information Systems_ 47.1 Springer, 2016, pp. 1–26
  * [24] Andreas Bader, Oliver Kopp and Michael Falkenthal “Survey and comparison of open source time series databases” In _Datenbanksysteme für Business, Technologie und Web (BTW 2017)-Workshopband_ Gesellschaft für Informatik eV, 2017
  * [25] Anthony Bagnall et al. “The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances” In _Data mining and knowledge discovery_ 31.3 Springer, 2017, pp. 606–660
  * [26] Lu Chen et al. “Pivot-based Metric Indexing” In _Proc. VLDB Endow._ 10.10, 2017, pp. 1058–1069 URL: http://www.vldb.org/pvldb/vol10/p1058-gao.pdf
  * [27] Marco Cuturi and Mathieu Blondel “Soft-dtw: a differentiable loss function for time-series” In _International Conference on Machine Learning_ , 2017, pp. 894–903 PMLR
  * [28] Søren Kejser Jensen, Torben Bach Pedersen and Christian Thomsen “Time series management systems: A survey” In _IEEE Transactions on Knowledge and Data Engineering_ 29.11 IEEE, 2017, pp. 2581–2600
  * [29] John Paparrizos and Luis Gravano “Fast and accurate time-series clustering” In _ACM Transactions on Database Systems (TODS)_ 42.2 ACM New York, NY, USA, 2017, pp. 1–49
  * [30] David Schultz and Brijnesh Jain “Nonsmooth analysis and subgradient methods for averaging in dynamic time warping spaces” In _Pattern Recognition_ 74 Elsevier, 2018, pp. 340–358
  * [31] Markus Brill et al. “Exact mean computation in dynamic time warping spaces” In _Data Mining and Knowledge Discovery_ 33.1 Springer, 2019, pp. 252–291
  * [32] Christian Garcia-Arellano et al. “Db2 event store: a purpose-built IoT database engine” In _Proceedings of the VLDB Endowment_ 13.12 VLDB Endowment, 2020, pp. 3299–3312
  * [33] Weiwei Jiang “Time series classification: Nearest neighbor versus deep learning models” In _SN Applied Sciences_ 2.4 Springer, 2020, pp. 1–17
  * [34] John Paparrizos, Chunwei Liu, Aaron J Elmore and Michael J Franklin “Debunking Four Long-Standing Misconceptions of Time-Series Distance Measures” In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ , 2020, pp. 1887–1905