Dear Reader.
This paper is an extended version of our ICDM 2016 paper [a]. We are making this version available in order to have more clear
results and discussions in comparison to its short version.
[a] Silva, D. F., Batista G. E. A. P. A. and Eamonn Keogh, “Prefix and Suffix Invariant Dynamic Time Warping”, in Proceedingsof the IEEE International Conference on Data Mining, 2016.

Prefix and Suffix Invariant Dynamic Time Warping
Diego F. Silva, Gustavo E. A. P. A. Batista

Eamonn Keogh

Universidade de São Paulo{diegofsilva, gbatista}@icmc.usp.br

University of California, Riversideeamonn@cs.ucr.edu

Abstract — While there exist a plethora of classification
algorithms for most data types, there is an increasing acceptancethat the unique properties of time series mean that the
combination of nearest neighbor classifiers and Dynamic Time
Warping (DTW) is very competitive across a host of domains,from medicine to astronomy to environmental sensors. While
there has been significant progress in improving the efficiency andeffectiveness of DTW in recent years, in this work we demonstratethat an underappreciated issue can significantly degrade theaccuracy of DTW in real-world deployments. This issue has
probably escaped the attention of the very active time series
research community because of its reliance on static highly
contrived benchmark datasets, rather than real world dynamic
datasets where the problem tends to manifest itself. In essence, theissue is that DTW’s eponymous invariance to warping is only true
for the main “body” of the two time series being compared.
However, for the “head” and “tail” of the time series, the DTW
algorithm affords no warping invariance. The effect of this is thattiny differences at the beginning or end of the time series (which
may be either consequential or simply the result of poor
“cropping”) will tend to contribute disproportionally to theestimated similarity, producing incorrect classifications. In thiswork, we show that this effect is real, and reduces the performanceof the algorithm. We further show that we can fix the issue with asubtle redesign of the DTW algorithm, and that we can learn anappropriate setting for the extra parameter we introduced. We
further demonstrate that our generalization is amiable to all the
optimizations that make DTW tractable for large datasets.

from the UCR time series archive [4]. Improvements on this(admittedly very useful) resource have been seen as sufficient towarrant publication of a new idea, but it would be better to see
success on these benchmarks as being only necessary to warrant
consideration of a new approach.
In particular, the way in which the majority of the datasets
were created and “cleaned” means that algorithms that do wellon these datasets can still fail when applied to real world
streaming data.
The issue lends itself to a visually intuitive explanation. Fig.
1 shows two examples from the Australian Sign Language
dataset aligned by DTW. We can see the utility of DTW here, as
it aligns the later peak of the blue (bold) time series to the earlier
occurring peak in the red (fine) time series. However, this figure
also illustrates a weakness of DTW. Because every point must
be matched, the first few points in the red sequence are forced tomatch the first point in the blue sequence.
10-1This region corresponds toonly 6% of the length of thesignals, yet it accounts 70.5%of the distance1
0-1

Keywords— Time Series, Dynamic Time Warping, Similarity
Measures

I. INTRODUCTION
Following the huge growth of applications based on
temporal measurements, such as Quantified Self and Internet ofThings [24], time series data are becoming ubiquitous even in
our quotidian lives. It is increasingly difficult to think of ahuman interest or endeavor, from medicine to astronomy, that
does not produce copious amounts of time series.
Among all the time series mining tasks, query-by-content is
the most basic. It is the fundamental subroutine used to support
nearest-neighbor classification, clustering, etc. The last decade
has seen mounting empirical evidence that the unique propertiesof time series mean that Dynamic Time Warping (DTW) is thebest distance measure for time series across virtually all
domains, from activity recognition for dogs [11] to classifying
star light curves to ascertain the existence of exoplanets [5].
However, virtually all current research efforts assume aperfect segmentation of the time series. This assumption isengendered by the availability of dozens of contrived datasets

Our solution: expand therepresentational power of DTW
to ignore a small fraction of theprefix (and suffix) of the signals
0

5

10

15

20

25

30

35

40

45

50

Fig. 1. top) Two time series compared with DTW. While the prefix of the red(fine) time series consists of only 6% of the length, it is responsible for 70.5%of the error. bottom) We propose to address this disproportionate appointing oferror by selectively ignoring parts of the prefix (and/or suffix)

While Fig. 1 does show the problem on a real data object,
the reader may wonder how common this issue is “in the wild”.
We claim that at least in some domains, this problem is very
common. For example, heartbeat extraction algorithms often
segment the signal to begin at the maximum of the QRS
complex [23]. However, as shown in Fig. 2, this location has
the greatest variability in its prefixes and suffixes.

0

40

80

120

160

Fig. 2. Three heartbeats taken from a one-minute period of a healthy male. The
beats were extracted by a state-of-the-art beat extraction algorithm [20], butthere is significant variation in the prefix (all three) and in the suffix (green vs.
the other two)Similar remarks apply to gait cycle extraction algorithms[25]. Likewise, star light curves, for which DTW is known to bevery effective, have cycles extracted by a technique called
universal phasing [19]. However, universal phasing has theunfortunate side effect of placing the maximum variance at theprefix and suffix of the signals.

ideas on synthetic and real data. Having shown our ideas are
effective, Section VII explains how to adapt state-of-the-art
lower bound functions to the distance measure proposed in thispaper, a critical step to maintain efficiency. Finally, in Section
VIII we offer conclusions and directions for future work.

In this work, we address this problem of uninformative andundesirable “information” contained just before and just after
the temporal measurement of informative data. For the sake ofclarity, we will refer to these unwanted values as prefix andsuffix, and use endpoints to refer to both.

II. TIME SERIES SUFFIX AND PREFIXOur approach is simple and intuitive, but highly effective.
We modify the endpoint constraint of Dynamic Time Warping(DTW) to provide endpoint invariance. The main idea behind
our proposal is allowing DTW to ignore some leading/trailingvalues in one or both of the two time series under comparison.
While our idea is simple, it must be carefully executed. It is clearthat ignoring too much (useful) data is just as undesirable aspaying attention to spurious data.
We note that somewhat similar observations were known to
the signal processing community when DTW was the state-ofthe-art technique for speech processing (in the 1980’s and 90’s
before being superseded by Markov models [16]). However, theimportance of endpoint invariance for time series seems to belargely unknown or underappreciated [10][17][18].

Most research efforts for time series classification assume
that all the time series in the training and test sets are carefully
segmented by using the precise endpoints of the desirable event[18][19][27][29]. Despite the ubiquity of time series datasetsthat fulfill such an assumption, in practical situations the exact
endpoints of events are difficult to detect. In general, a perfectly
segmented dataset can only be achieved by manual
segmentation or some contrivance that uses external
information.
To see this, we revisit the Gun-Point dataset, which has beenused in more than two hundred papers to test the accuracy oftime series classification [4]. As shown in Fig. 3, the data objects
considered here do have perfectly flat prefixes and suffixes.
However, these were obtained only by carefully prompting theactor’s movements with a metronome that produced an audiblecue every five seconds.

We can summarize the main contributions of this paper asfollows:
 We draw the data mining community’s attention to theendpoint invariance, which seems to be a little or no
considered issue;
 We propose a modification of the well-known algorithm
Dynamic Time Warping to provide invariance to suffix
and prefix;
 Although simple and intuitive, we show that our method
can considerably improve the classification accuracy
when warranted, and just as importantly, our ideas do not
reduce classification accuracy if the dataset happens to
not need endpoint invariance; Unlike other potential fixes, our distance measure
respects the property of symmetry and, consequently, canbe applied in a multitude of data mining algorithms withno pathological errors caused by the order of the objects
in the dataset; In spite of the fact that we must add a parameter to DTW,
we show that it is possible to robustly learn a good value
for this parameter using only the training data.
The remainder of this paper is organized as follows. Section
II formalizes the concept of time series suffix and prefix andshows intuitive examples of how it affects the distancemeasurement, and therefore, the classification accuracy. Section
III summarizes the main concepts necessary to understand our
proposal (in particular, a detailed review of the Dynamic Time
Warping algorithm). Section IV places our ideas in the context
of related work. We explain our proposed method in detail in
Section V. In Section VI, we empirically verify the utility of ourSynchronizing
BEEP frommetronome

0

Synchronizing
BEEP frommetronome

50

100

150

Fig. 3. The ubiquitous Gun-Point dataset was created by tracking the hand of anactor (top). However, the perfectly flat prefix and suffix were due to carefully
training the actor to have her hand immobile by her side one second before andone second after the cue from a metronome (bottom)

In more realistic scenarios, the movement of pointing a
gun/finger must be detected among several different
movements. Before drawing the weapon, the actor could berunning, talking on a cell phone, etc.
For example, consider the scenario in which somemovement was performed just before the weapon was aimed. In
addition, another movement started immediately after the gun
was returned to the holster. In this case, the time series could
have a more complex shape as shown in Fig. 4. As visually
explained in Fig. 1, it is clear that prefix and suffix would greatly
prejudice the distance estimation in this case.
prefix“pointing a
gun/finger”
event

suffixFig. 4. Example of a time series containing the event to be classified (in blue)
and prefix and suffix information (in red)Another possible issue that can result from automatic
segmentation is illustrated in Fig. 5. In this case, the algorithm
used to extract the time series was too “aggressive” and madethe mistake of truncating the last few observations of the eventof interest. Obviously, a similar issue could also happen at the
beginning of the signal.

prefix“pointing a
gun/finger”
event

Fig. 5. An example of an extracted time series containing an incomplete subsetof the shape to be classified (in blue) and a prefix information (in red)In this case, the time series is missing its true suffix. Even
with such missing information, the shape that describes the
beginning of the action may be enough such that it will beclassified correctly. However, the object that would otherwise
be considered its nearest neighbor may contain information of
the entire movement, as shown in Fig. 4. To classify the badly
cropped item in Fig. 5 correctly, a distance measure must avoid
matching the last few observations of the complete event to thevalues observed in our badly segmented event. In Section V wewill show how our method can solve these issues.
III. DEFINITIONS AND BACKGROUND
A time series x is a sequence of n ordered values such that
x=(x1,x2,…,xn) and xt∈ ℝ for any t∈[1,n]. We assume that twoconsecutive values are equally spaced in time or the interval
between them can be disregarded without loss of generality. For
clarity, we refer each value xt as observation.
The Dynamic Time Warping (DTW) algorithm is arguably
the most useful distance measure for time series analysis1. For
example, mounting empirical evidence strongly suggest that thesimple nearest neighbor algorithm using DTW outperforms
more “sophisticated” time series classification methods in awide range of application domains [29].
In contrast to other distance measures, such as those in the
Lp-norm family, the DTW computes a non-linear alignment
between the observations of the two time series being compared.
In other words, while Lp-norm distances are only able tocompare the value xt to a value yt of a time series y, DTW is able
to compare xt to ys such that t≈s.
To compute the optimal non-linear alignment between a pairof time series x and y, with lengths n and m respectively, theDTW typically bound to the following constraints:
 Endpoint constraint. The matching is made for the entire
length of time series x and y. Therefore, it starts at the pairof observations (1,1) and ends at (n,m);
 Monotonicity constraint. The relative order ofobservations must be preserved, i.e., if s1<s2, thematching of xt with ys1 is done before matching xt withys2;
 Continuity constraint. The matching is made in one-unit
steps. It means that the matching never “jumps” one ormore observations of any time series.
The calculation of DTW distance is performed by a dynamic
programming algorithm. The initial condition of such analgorithm is defined by Equation 1.

1

Note that DTW subsumes the second most useful measure, the Euclidean
distance, as a special case.

∞, if (i = 0 or j = 0) and i ≠ jdtw(i,j)= {0, if i = j = 0

In order to find the optimal non-linear alignment between theobservations of the time series x and y, DTW follows therecurrence relation defined by Equation 2.



dtw(i-1,j)dtw(i,j)= c (xi ,yj ) +min { dtw(i,j-1) 
dtw(i-1,j-1)

where i∈ [1,n] and j∈ [1,m], m being the length of the timeseries y. The partial c(xi,yj) represents the cost of matching two
observations xi and yj and is calculated by the squared Euclidean
distance between them. Finally, the DTW distance returned is
DTW(x,y)=dtw(n,m).
An additional constraint commonly applied to DTW is thewarping constraint. This constraint limits the time difference
that the algorithm is allowed to match the observations. In thematrix view of DTW, this constraint limits the algorithm tocalculate the values of the DTW matrix in a region close to its
main diagonal. The benefit of using a warping constraint is two
fold: the DTW calculation takes less time (as it is not necessary
to calculate values for the entire distance matrix) and it avoids
pathological alignments. For example, when comparing
heartbeats, we want to allow a little warping flexibility to beinvariant to small (and medically irrelevant) changes in timing.
However, it never makes sense to attempt to align ten heartbeats
to twenty-five heartbeats. The warping constraint prevents suchdegenerate solutions. As a practical confirmation of its utility
using the constraint, we note that it has been shown to improveclassification accuracy [18].
The most common warping constraint for DTW is the
Sakoe-Chiba warping window [21]. The use of warping
constraints adds a parameter to be set by the user. However,
several studies show that small windows (usually smaller than10%) are usually a good choice for nearest neighborclassification [18].
IV. RELATED WORKThe utility of relaxing the endpoint constraint of DTW has
been previously noticed by the signal processing community, inthe context of speech [7] and music analysis [14]. However, theissue seems to be unknown or glossed over in time series data
mining.
The time series mining method that shares more similarities
to our proposal is the open-end DTW (OE-DTW) [26].
However, OE-DTW was proposed to match incomplete timeseries to complete references. In other words, such a method isbased on the assumption that we can construct a training set withcarefully cropped time series and we can know the exact pointthat represents the beginning of the time series to be classified.

Specifically, OE-DTW is a method that allows ignoring any
amount of observations at the end of the training time series. The
final distance estimate is the value represented bymin0≤i≤m DTW(n,i) i.e., the final distance is the minimum value
in the last column of the DTW matrix.
A weakness of OE-DTW is that it does not consider the
existence of prefix information. A modification of the OE-DTW
called open-begin-end DTW (OBE-DTW) or subsequence
DTW [13] mitigates this issue. OBE-DTW allows the match ofobservations to start at any position of the training time series.
To allow DTW to do this, the algorithm needs to initialize theentire first column of the DTW matrix with zeros.
Although OBE-DTW recognizes that both prefix and suffix
issues may exist, it only addresses the problem in the training
time series. A more important observation is that OBE-DTW isnot symmetric, which severely affects its utility. For example,
the results obtained by OBE-DTW in any clustering algorithm
are dependent on the order in which the algorithm processes thetime series. To see this, consider the hierarchical single-linkage
clustering algorithm. Fig. 6 shows the result of clustering thesame set of five time series objects from the Motor Current
dataset (c.f. Section VI.B.1), presented in different orders to theclustering algorithm. Specifically, the distance between the timeseries x and y is calculated by OBEDTW(x,y) in the first case andby OBEDTW(y,x) in the second. Note that the results arecompletely different, a very undesirable outcome.

Similar to the OBE-DTW, the method proposed in this paper
is based on a relaxation of the endpoint constraint. However, ourmethod is symmetric and strictly limits the amount of the signalsthat can be ignored, preventing the meaningless alignments
shown in Fig. 7. Fig. 8 shows a comparison of the results
obtained by the classic DTW, the OBE-DTW, and the distancemeasure proposed in this work when used to cluster the timeseries data considered in Fig. 6.
DTW

OBE-DTW

Our proposal

Fig. 8. Clusterings on a toy dataset using the classic DTW (left), OBE-DTW(center), and the distance measure proposed in this paper (right). Note that our
method achieves a perfect and intuitive separation of the different classes

Finally, other algorithms skip the matching between
observations, but they were proposed for different scenarios.
Specifically, some algorithms were proposed to avoid errors ofmeasurements, noise, occlusion, among other problems that may
occur along the time series. Usually, such methods require a gap
penalty or a threshold to decide whether two points of the timeseries should be considered a match or not. This is the case, forinstance, of the Longest Common Subsequence (LCSS) [12].
Because they do not deal directly with the endpoint differences
and the gap penalty is usually hard to define, we do not use thesealgorithms in our experimental evaluation.
V. PREFIX AND SUFFIX-INVARIANT DTW (Ψ-DTW)

Fig. 6. Clustering results of the same dataset by using OBE-DTW. The difference
between the results is given by the fact that they were obtained by presenting thetime series in a different order to the clustering algorithm

In addition to this issue, OBE-DTW has one other fatal flaw.
In essence, it can be “too invariant,” potentially causing
meaningless alignments in some cases. Fig. 7 shows an extreme
example of this. In the top figure, all observations of flat line
match to a single observation in the sine wave, and the DTW
distance obtained is 0.07. In the bottom figure, we reverse theroles of reference and query. This time, all observations of thesine wave match to a single observation in the flat line, and theDTW distance obtained is 69.0. We observe a three orders ofmagnitude difference in the DTW results.
1.5
0
-1.5
0

10

20

30

40

50

60

70

1.5
0
-1.5
0

10

20

30

40

50

60

70

Fig. 7. The OBE-DTW alignment for the same pair of time series. In the first(top), a sine wave is used as reference and the flat line is used as query. In thesecond (bottom), the same sine wave is used as query while the flat line is used
as reference

While there are many different methods proposed for timeseries classification (decision trees, etc.), it is known that thesimple nearest neighbor is extremely competitive in a wide
range of applications and conditions [29]. Given this, the only
decision left to the user is the choice of the distance measure.
In most cases, this choice is guided by the invariances
required by the task and domain [3]. In conjunction with simple
techniques, such as z-normalization, DTW can provide several
invariances like amplitude, offset and the warping (or local
scaling) itself.
In this work, we address what we feel is the “missing
invariance,” the invariance to spurious prefix and suffix
information. Given the nature of our proposal, we call our
method Prefix and Suffix-Invariant DTW, or simply PSI-DTW(or ψ-DTW).
The relaxed version of the endpoint constraint proposed inthis work is defined as the following.
Relaxed endpoint constraint. Given an integer value r, thealignment path between the time series x and y starts at any
pair of observations in {(1,c1+1)}∪{(c1+1,1)} and ends at
any pair in {(n-c2,m)}∪{(n,m-c2)}, such that c1 and c2∈[0,r].

This relaxation of the endpoint constraint can avoid
undesirable matches at the beginning and the end of any x or ytime series by removing the obligation for the alignment path tostart and end with specific pairs of observation, namely the first
and the last pairs. The value r used in this definition is therelaxation factor parameter that needs to be defined by the user.
We recognize the general undesirability of adding a newparameter to an algorithm. However, we argue it is necessary(c.f. Section IV). In addition, we show that we are able to learn
an appropriate r solely from the training data. We will return tothis topic in Section VI.
An important aspect of the proposed endpoint constraint is
the fact that, by definition, the same number of cells is “relaxed”
for both column and row in the cumulative cost matrix. This iswhat guarantees the symmetry of ψ-DTW. If the number ofrelaxed columns and rows was different, the starting andfinishing cells of the alignment found by ψ-DTW(x,y) could beoutside of the region defined by the endpoint constraint in thecost matrix used by ψ-DTW(y,x).
The relaxation of endpoints slightly affects the initializationof the DTW estimation algorithm defined in Equation 1. To
accomplish the new constraint, the initialization of DTW needs
to be changed to Equation 3.

∞, if i = 0 and j > r
0, if i = 0 and j ≤ r
dtw(i,j)= {∞, if j = 0 and i > r
0, if j = 0 and i ≤ rAfter this initialization, the recurrence relation to fill thematrix is unchanged; it is exactly the same as defined by
Equation 2.
Finally, the ultimate distance estimate is not necessarily
obtained by retrieving the value in dtw(n,m). This minor
modification can be directly obtained by the definition of the
proposed relaxed endpoint constraint. Formally, the final
distance calculation is given by Equation 4.

Ψ-DTW(x,y,r)=min(i,j)∈finalSet[dtw(i,j)],

finalSet = {(n-c1 ,m)}∪{(n,m-c2 )} ∀ c1 ,c2 ∈ [0,r].



The algorithm to calculate ψ-DTW is simple. For
concreteness, TABLE I. describes it in detail.
TABLE I.

Ψ-DTW ALGORITHM

Procedure ψ-DTW(x,y,r)
Input: Two user provided time series, x and y and the relaxation factor
parameter r
Output: The ψ-DTW distance between x and y
1 n←length(x), m←length(y)2 M ← infinity_matrix(n+1,m+1)
3 M([0,r],0) ← 0
4 M(0,[0,r]) ← 0
5 for i ← 1 to n
for j ← 1 to m
6
M(i,j) ← c(xi,yj) + min(M(i-1,j-1),M(i,j-1), M(i-1,j))
7
8 minX ← min(M([n-r,n],m)), minY ← min(M(n,[m-r,m]))9 return min(minX,minY)

The algorithm starts by defining the variables used to accessthe length of time series (line 1) and the DTW matrix according
to Equation 3 (lines 2 to 4). The for loops (lines 5 to 7) fill thematrix according to the recurrence relation defined in Equation
2. Finally, the algorithm finds the minimum value in the region
defined by the new endpoint constrained and returns it as the
distance estimate (lines 8 and 9). To implement the constrained
warping version of this algorithm, one only needs to modify theinterval of the second for loop (line 6) according to the constraint
definition.
Note that the proposed method is a generalization of DTW,
thus it is possible to obtain the classic DTW by our method.
Specifically, if r=0, the final result of our algorithm is exactly
the same as the classic DTW.
VI. EXPERIMENTAL EVALUATION
We are committed to reproducibility, thus we have madeavailable all the source code, datasets, detailed results andadditional experiments in a companion website for this work[22]. In addition to reproducing our experiments, the interested
reader can use our code on their own datasets. We implemented
all our ideas in Matlab, as it is ubiquitous in the data mining
community.
To test the robustness of our method, we compare its
performance against the accuracy obtained by the classic DTW,
in both unconstrained- and constrained-warping versions (c.f.
Section III). We refer to the constrained versions of thealgorithms with names containing the letter c. For clarity, cDTW
refers to the DTW with warping constraint and ψ-cDTW stands
for the constrained version of ψ-DTW. In addition, we present
results obtained using OBE-DTW.
We are not directly interested in studying the effect of
warping window width on classification accuracy. The value ofthe warping window width parameter has been shown to greatly
affect accuracy, but it has also been shown to be easy to learn agood setting for this parameter with cross validation[18][27][29]. For simplicity, we fixed it as 10% of the length of
the query time series by default.
However, this setting limits the choice of the relaxation
factor to ψ-DTW. For any relaxation factor that is greater thanor equal to the warping length, the final distance estimate does
not change. It happens because the “open” cells outside theregion defined by warping window are ignored by the algorithm.
For this reason, when we wanted to test the effect of larger
relaxation factors, the warping window used in the experiment
was set by the same value as r.
We divide our experimental evaluation into two sections.


In order to clearly demonstrate that our algorithm isdoing what we claim it can, we take perfectly cropped
time series data and add increasing amounts of spurious
endpoint data. This experiment simulates the scenario in
which the segmentation of time series is not perfect, i.e.,there are endpoints that may represent random
behaviors;The experiments above will be telling, but unless real
datasets have the spurious endpoint problem, they will

be of little interest to the community. Thus, we apply ψDTW on real datasets that we suspect have a highprobability of the presence of spurious endpoints.
For clarity of presentation, we have confined this work to thesingle dimensional case. However, our proposal can be easily
generalized to multidimensional data.
A. The Effect of ψ-DTW on Different Lengths of Endpoints
As noted above, the UCR Time Series Archive has been
useful to the community working on time series classification[4]. However, in general, the highly contrived procedures used
to collect and/or clean most of the datasets prevent theappearance of prefixes and suffixes (recall Fig. 3). For thisreason, the impact of endpoints cannot be directly evaluated by
the use of such datasets.
However, such “endpoint-free” data create a perfect starting
point to understand how different amounts of uninformative data
can affect both DTW and ψ-DTW. To see this, we consider
some datasets that are almost certainly free of specious prefix or
suffix information. To these we prepend and postpend random
walk subsequences with length varying from 0% to 50% of theoriginal data. Next, we compared the accuracy obtained using
the nearest neighbor classification for each modified dataset
using both DTW and ψ-DTW. At each length of added data, weaverage over three runs with newly created data.
At this point, we are not learning the parameter r. Instead,
we fixed both the relaxation factor and warping constraint length
as 10% of the time series being compared.
Intuitively, as we add more and more spurious data, we
expect to see greater and greater decreases in accuracy.
However, we expect that ψ-DTW degrades slower. In fact, thisis the exact behavior observed in our experiments. Fig. 9 shows
the results on the Cricket X dataset.
0.8

Accuracy

0.7

0.6

y-cDTW

0.5

y-DTW
cDTW

0.4

DTW
0

0.1

0.2

0.3

0.4

0.5

Relative length of added random walk

Fig. 9. The accuracy after padding the Cricket X dataset with increasing lengthsof random walk data

For brevity, here we show the results on only one dataset.
However, we note that it describes the general behavior of theresults obtained in other datasets. We invite the interested reader
to review some additional experiments in our website [22].
B. Case Studies
In the previous experiment, we showed the robustness of ψDTW in the presence of spurious prefix and suffix informationin artificially contrived time series data. In this section, we
evaluate our method on real data.
The datasets we consider were extracted in a scenario in
which we do not have perfect knowledge or control over the
events' endpoints. In some cases, the original datasets wereobtained by recording sessions similar to the Gun-Point dataset(c.f. Section II), in which the invariance to endpoints is enforcedby the data collection procedure. In this case, we model the realworld conditions by ignoring the external cues or annotations.
In particular, we simulated a randomly-ordered stream of events
followed by a classic subsequence extraction step. For thisphase, we considered the simple sliding window approach. For
additional details on the extraction phase, please refer to [22].
In keeping with common practice, we adopted the use ofdictionaries as training data. A data dictionary is a subset of theoriginal training set containing only its most relevant examples.
The utility of creating dictionaries is two-fold [8]: it makes theclassifier faster and the accuracy obtained by dictionaries istypically better than that obtained by using all the training data,
which may contain outliers or mislabeled data.
To compute the relevance of training examples to theclassification task, we used the SimpleRank function [27]. Thisfunction returns a ranking of exemplars according to theirestimated contribution to the classification accuracy. Then, we
selected the top-k time series of each class in the dictionary, withk empirically discovered for each dataset.
The main intuition behind SimpleRank is to define a scorefor each exemplar based on its neighborhood. For each exemplar
tj, its nearest neighbor s is “rewarded” if it belongs to the sameclass, i.e., s is used to correctly classify tj. Otherwise, s is
“penalized” by having its score decreased. Equation 5 formallydefines the SimpleRank function.

rank(s)= ∑j {1, if class(s)=class(tj )-2num_classes - 1, otherwise





The length of subsequences and the size of the dictionary foreach dataset were chosen in order to obtain the best accuracy inthe training set by using cDTW. In addition, the SimpleRank
used to construct the dictionaries was also implemented by using
the classic cDTW instead of the distance measure proposed inthis work. This was done to ensure we are not biasing our
experimental analysis in favor of our method.
Once created the dictionary, we need to estimate a goodvalue for the parameter r. For this, we experimented with a wide
range of possible values. We set r as a relative value to the lengthof the time series under comparison. Specifically, we used a setof values rlr ∈{0,0.05,0.1,0.15,0.2,0.25,0.3,0.35,0.4,0.45,0.5} ,such that r = ⌈n*rlr ⌉, where n is the length of the time series.
We limited the value of r to be at most half the number ofobservations of the time series in order to avoid meaninglessalignments, such as the ones obtained by OBE-DTW in theexample illustrated in Fig. 7.
Besides defining a range of values to evaluate, we need todefine a procedure to perform such evaluation. Note that the
choice of the size of the dictionary is a crucial determinant of thetime complexity of the algorithm. For this reason, the number ofexamples in the dictionary tends to be small in order to keep thealgorithm fast, which makes learning r difficult if we use thedata in the dictionary exclusively.

0.95

Accuracy

In order to learn the value of r, we used a validation set
containing all the training time series but those chosen as part ofthe dictionary. However, we notice that cross-validation
techniques on the training set lead to similar results.

0.9
0.85
0.8

The data in question includes 21 classes representing
different operating conditions. In addition to a class that
represents (a slight) diversity of healthy operation, the otherclasses represent different defects in the apparatus (in particular,
one to ten broken bars and one to ten broken end-ringconnectors).
The original data used in this study is segmented, but withno attention paid to avoiding endpoints inconsistences.
Therefore, in this case, we did not use the approach of simulating
a data stream. We segmented the original time series using astatic window placed in the middle of each time series. With thisprocedure, the signals have different endpoints in each different
length we consider. Fig. 10 shows the classification results.
0.5

Accuracy

0.4

0.3
0.2

0.1
0
1100

1200
DTW

1300
Time Series Length
cDTW

y-cDTW

1400

y-DTW

1500
OBE-DTW

Fig. 10. Classification results obtained by varying the time series length on theMotor Current dataset

Given that this dataset is a very clear case of badly-defined
endpoints, these results show the robustness of our proposal.
Over all lengths we experimented with, ψ-DTW beats DTW andOBE-DTW by a large margin. Specifically, ψ-DTW can achieve
accuracy rates as high as 40% while the best result achieved by
the other methods is lower than 12%.

0.75
150

200
DTW

250
Time Series Length
cDTW

y-cDTW

300

y-DTW

350
OBE-DTW

Fig. 11. Classification results obtained by varying the time series length on theSony AIBO Robot Surface dataset

In the second scenario, the aim is the identification of theactivity performed by the robot. In this case, the target classes
are the robot playing soccer, standing in a stationary position,
trying to walk with one leg hooked, and walking straight into afixed wall. Fig. 12 shows the results obtained in this scenario.
0.9

Accuracy

1) Motor Current Data
Our first case study considers electric motor current signals.
This dataset has long been a staple of researchers interested inprognostics and novelty detection [15]. We refer the reader
interested in the procedure to generate such data to [6].

0.85
0.8
0.75
0.7
150

200

DTW

250
Time Series Length

cDTW

y-cDTW

300

y-DTW

350

OBE-DTW

Fig. 12. Classification results obtained by varying the time series length on theSony AIBO Robot Activity dataset

In both scenarios evaluated in this study, the results obtainedby ψ-DTW are generally better than the classic DTW. However,there is an important caveat to discuss. Despite theimprovements in accuracy in most time series lengths, theaccuracy obtained by ψ-DTW was the same or slightly worse
than the performance of the classic DTW in a few experiments.
This happened because our procedure to learn the relaxation
factor was not able to find a more suitable value in these cases.
Even in these cases, the poor choice of 𝑟 did not significantly
affect the classification accuracy.
It is important to notice that the OBE-DTW performed
similar or slightly better than ψ-DTW in the robot surface
dataset. However, as we can see along this experimental section,
this is the only case in which it occurs.

2) Robot Surface and Activity Identification
In this case study, we consider the classification of signals
collected by the accelerometer embedded in a Sony ERS-210
Aibo Robot [28]. This robot is a dog-like model equipped witha tri-axial accelerometer to record its movements.

3) Gesture Recognition
Gesture recognition is one of the most studied tasks in thetime series classification literature. The automatic identificationof human gestures has become an increasingly popular mode ofhuman-computer interaction.

Using the streaming data sets collected by this robot, weevaluated the classification accuracy in two different scenarios:
surface and activity recognition. In the former scenario, the goal
is to identify the type of surface in which the robot is walking
on. Specifically, the target classes for this problem are carpet,
field, and cement. Fig. 11 shows the results for this dataset.

In this study, we used the Palm Graffiti Digits dataset [1],which consists of recordings of different subjects “drawing”
digits in the air while facing a 3D camera. The goal of this task
is the classification of the digits drawn by the subjects. Fig. 13
shows the results.

there is also a notable increase in the interest of human activity
analyses using this kind of equipment.

0.35
0.3
0.25

0.2
100

125

DTW

150
Time Series Lengthy-cDTW

cDTW

175

y-DTW

200

OBE-DTW

Fig. 13. Classification results obtained by varying the time series length on thePalm Graffiti Digits dataset

Similar to our findings with the robot data, the accuracy rates
obtained by our proposal are usually better than the obtained by
the classic DTW. In few cases, the accuracy is slightly worse.
However, most important is the robustness of ψ-DTW to thecases where the prefixes and suffixes seem to significantly affectthe classification. For instance, there is an expressive loss of
accuracy obtained by the classic DTW in the dataset containing
time series with 150 observations. The loss is notably less drastic
when we using ψ-DTW. In addition, the performance of OBEDTW in this dataset is significantly worse than any otheralgorithm.
4) Sign Language Recognition
Another specific scenario with gesture data used in this workis the recognition of sign language. A sign language is analternative way to communicate by gestures and body languagethat replace (or augment) the acoustic communication. In thiswork we used a dataset of Australian Sign Language(AUSLAN) [9]. The original dataset is composed of signs
separately recorded in different sections. We used 10 arbitrarily
chosen signs of each recording session displaced as a data
stream.
0.6

Accuracy

0.55
0.5
0.45

0.4
0.35
50

100

DTW

150
Time Series Lengthy-cDTW

cDTW

200

y-DTW

250

OBE-DTW

Fig. 14 shows the results.
0.6

Accuracy

0.55
0.5
0.45

0.4

In this final case study, we investigate the robustness of ψDTW in the recognition of human activities using smartphone
accelerometers. For this purpose, we used the dataset that first
appeared in [2]. Originally, the recordings are composed of 128
observations of three coordinates of the device’s accelerometers.
In our study, we used the x-coordinate disposed in a streaming
fashion. Fig. 15 shows the results.
0.6

Accuracy

Accuracy

0.4

0.56

0.52
0.48
150

DTW

150
Time Series Length

cDTW

y-cDTW

200

y-DTW

y-cDTW

225

y-DTW

250
OBE-DTW

Again, the accuracy achieved by ψ-DTW is better than theaccuracy obtained by the classic DTW and the OBE-DTW in all
the cases for this dataset.
6) Summary of the Results and Hypothesis Test
The results presented so far show that ψ-DTW achieves
better results than the classical DTW and the OBE-DTW in mostof the experimented cases. In the case that such results are notclearly strong, a hypothesis test on the accuracies obtained byboth methods may be used. For this, we performed a paired
Wilcoxon signed-rank test for comparing the performances ofeach combination between DTW, cDTW and OBE-DTW
against ψ-DTW and ψ-cDTW. Using a confidence factor of
95%, the test rejected the null hypothesis (that the mean ranks
are similar) for all the comparisons.
The results analyzed so far regard to each pair of dataset andtime series length. However, it is interesting to analyze theaccuracies obtained for each dataset, considering the best timeseries length. To evaluate this, we used the validation procedure
applied to learn r as the method to choose the time series length
to assess the performance of ψ-DTW. For comparison, we used
the best accuracy obtained by OBE-DTW and DTW. Note that
this analysis is favoring the competing algorithms, given that weused an oracle instead of learning the best series length for thesemethods. TABLE II. shows the result of this experiment.
TABLE II.

100

200
Time Series Length
cDTW

Fig. 15. Classification results obtained by varying the time series length on the
Human Activity Recognition dataset

0.35
50

175
DTW

ACCURACIES OBTAINED BY OBE-DTW, DTW, AND Ψ-DTW

250

OBE-DTW

Fig. 14. Classification results obtained by varying the time series length on the
AUSLAN dataset

For this dataset, we can easily verify the superiority of theaccuracies obtained by relaxing the endpoint constraint incomparison to the other methods. More importantly, the best
accuracy rates were significantly superior when using ψ-DTW.
5) Human Activity Recognition
Due to the growth in the use of mobile devices containing
movement sensors (such as accelerometers and gyroscopes),

DatasetAUSLAN
Human Activity
Motor Current
Palm Graffiti
Robot Activity
Robot Surface

OBE-DTW

DTW

ψ-DTW

cDTW

ψ-cDTW

0.503
0.555
0.114
0.262
0.839
0.950

0.500
0.558
0.119
0.374
0.845
0.846

0.579
0.575
0.400
0.355
0.854
0.910

0.490
0.566
0.119
0.363
0.822
0.842

0.514
0.578
0.405
0.363
0.833
0.842

VII. LOWER BOUNDING OF Ψ-DTW
One of the biggest concerns while designing a new distancemeasure is time efficiency. This is more prevalent in our casesince we are proposing a modification of Dynamic Time
Warping, an O(n2) algorithm. In fact, a straightforwardimplementation of the nearest neighbor algorithm under DTW
makes its use impractical on large datasets. For this reason, thecommunity has proposed several methods to improve theefficiency of the similarity search under DTW.
Specifically, [17] shows that the combination of few simple
techniques for speeding-up similarity search makes possible tohandle truly massive data under DTW. We claim that all thesemethods can be applied to the ψ-DTW with subtle or no
modifications.
Some of the most important speed-up methods rely on theuse of a lower bound (LB) function. An LB function returns avalue certainly lower or equal to the true DTW between two
objects. Our algorithm is amenable to adaptation of LB
functions.
Before explaining how to adapt LB functions to ψ-DTW, we
briefly explain the intuition behind the use of LB on time series
similarity search. Consider that we have a variable best-so-far
that stores the distance to the nearest neighbor know up to thecurrent iteration of the search algorithm. We can use thisinformation to decide if we can avoid the expensive calculationof DTW. In order to do this, for each time series in the training
set, we first calculate the LB between it and the query. Clearly,
if the LB function returns a value greater than the best-so-far,
the training object is not the nearest neighbor of the query.
Therefore, the current object can be discarded before having its
distance to the query estimated. We can extend this to a k-nearest
neighbor scenario by simply replacing the best-so-far by the
distance to the k-th nearest object known at that moment.
Now we are in position to answer the question “How can weuse previously proposed LB functions with ψ-DTW?”.
We first note that ψ-DTW actually lower bounds the DTW,
as exemplified in Fig. 16. From a practical standpoint, thealignment path that starts at the first pair of observations andfinishes by matching the last one is a possible alignment foundby ψ-DTW that correspond to the exact classic DTW. Any otheralignment found is considered optimal only in the case in which
it provides a smaller value than the one obtained by DTW. Thissituation occurs when our method disregards some pair ofobservations that contributes to the total cost of matching.
300

DTW
distance

200

Ψ-DTW
distance

Ui =



Li =

i-w≤j≤i+w

max

(qj )

min

(qj )

i-w≤j≤i+w, 1 ≤ i ≤ nwhere w is the length of the warping constraint window. Clearly,
the partials i-w and i+w are restricted to the extent of the query.
Fig. 17 exemplifies the upper and lower sequences of a given
query time series.
q

U

L

0

5

10

15

20

25

30

35

40

45

50

Fig. 17. Upper and lower sequences of a given query time series q estimated by
LB_KeoghOnce the envelope is calculated, we are in the position toestimate the value of the LB function. For each time series t to
be compared to the query q, the value LB_Keogh is calculated
as the Euclidean distance between the observations of t that falls
outside the envelope and the nearest upper or lower sequence.
Fig. 18 illustrates this step in the comparison of the previously
used query q and a specific time series t.
U
t
L
0

5

10

15

20

25

30

35

40

45

50

Fig. 18. The LB_Keogh is calculated by using the values of the time series t thatfall outside the region bounded by the envelope

The only issue in directly applying LB_Keogh to lower
bound ψ-DTW is the fact that it is constrained by the classic
endpoint constraint of DTW. Therefore, in order to adapt
LB_Keogh to our method, we need to relax its endpoints. Since
ψ-DTW can skip the matching of the first and last r observations
in either q or t, the LB function should ignore these values. We
call the adapted LB function ψ-LB_Keogh, and define it
formally in Equation 7.
(ti -Ui )2 , if ti >Ui

2
ψ-LB_Keogh(q,t)= ∑n-r
i=r+1 { (L -t ) , if t <L 



i i

i



i

0 otherwise
The only difference between both LB functions is the rangeof i. Fig. 19 illustrates the ψ-LB_Keogh between q and t.
U

100
0

t
0

200

400

600

800

1000

1200

1400

Fig. 16. The distance between all the pairs of fifty time series objects in the
AUSLAN dataset sorted by their DTW distances. In this experiment, we usedboth warping constraint and relaxation factor as 10% of the length of time series

For this reason, it is not possible to apply most of the known
LB functions directly to our method. Adapting an LB functionto ψ-DTW requires the analysis of the possible first and last pairsof observations. For sake of exemplification, we will adopt themost widely used LB function, the LB_Keogh [10].
The calculation of LB_Keogh consists of two main steps.
The first step is the estimation of an envelope to a given query
time series q of length n. Specifically, the envelope is composedof an upper sequence U=(U1,U2,…,Un) and a lower sequence
L=(L1,L2,…,Ln) defined by Equation 6.

L
0

5

10

15

20

25

30

35

40

Fig. 19. ψ-LB_Keogh ignores the values in the dashed regions

45

50

To be effective, an LB function has to present the following
properties: (i) its calculation is fast; (ii) and it is tight, i.e., itsvalue is close to the true DTW. Particularly, the pruning powerof a lower bound function is directly related to its tightness.
To demonstrate the tightness of ψ-LB_Keogh, we compared
it with the tightness of LB_Keogh for all the study cases in
Section VI.B. We quantified the tightness of the LBs by dividingthem by the corresponding DTW distances. In this experiment,
we set the warping window as 10% of the time series length. The
relaxation factor takes the same value. TABLE III. shows theresults obtained in the training set with the shortest time series
used in each study case.
TABLE III. TIGHTNESS OF LB_KEOGH AND Ψ-LB_KEOGH
DatasetAUSLAN
Human Activity
Motor Current
Palm Graffiti Digits
Sony Robot Activity
Sony Robot Surface

LB_Keogh

ψ-LB_Keogh

0.522
0.173
0.259
0.549
0.120
0.174

0.484
0.152
0.292
0.490
0.110
0.151

From these results, we can note that the tightness of bothmethods is similar. In fact, ψ-LB_Keogh is even tighter than
LB_Keogh in one of the experimented datasets. This indicatesthat endpoint constraint relaxation does not impair the tightnessof ψ-LB_Keogh.
VIII. CONCLUSION
In this paper, we proposed a modification of the endpoint
constraint of DTW to make it suffix- and prefix-invariant. In
addition to be simple and intuitive, our method is quite effective.
Experimental results show that our method outperforms theclassic DTW by a large margin in datasets that contain spurious
endpoints. In addition, we demonstrated that the distanceobtained by our method can be tightly lower bounded by a slight
modification of the current lower bounds of DTW, whichindicates that our modified DTW is tractable for large datasets.
For the sake of clarity and brevity in this work we only
discussed the application of our algorithm to classification.
However, it can also be applied to a large variety of tasks, suchas clustering, motif discovery, outlier detection, etc. We leavethose explorations, including discussions on how to set theparameter r for each task, for future work.
REFERENCES
[1]

[2]

[3]

[4]

[5]
[6]

[7]

[8]

J. Alon, V. Athitsos, Q. Yuan, and S. Sclaroff, “A unified framework forgesture recognition and spatiotemporal gesture segmentation”. IEEE T.
Pattern. Anal. vol. 31, no. 9, pp. 1685-1699, 2009.
D. Anguita, A. Ghio, L. Oneto, X. Parra, and J. L. Reyes-Ortiz, “Humanactivity recognition on smartphones using a multiclass hardware-friendly
support vector machine”, in Proceedings of the International Workshop
of Ambient Assisted Living, 2012, pp. 216-223.
G. E. A. P. A. Batista, E. Keogh, O. M. Tataw, and V. M. A. Souza, “CID:
an efficient complexity-invariant distance for time series”, Data Min.
Knowl. Discov., vol. 28, no. 3, pp. 634-669, 2014.
Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall, A. Mueen, and G. E.
A. P. A. Batista, “The UCR Time Series Classification Archive”, 2015,
URL www.cs.ucr.edu/~eamonn/time_series_data/
A. Debray, and R. Wu, “Astronomical implications of Machine
Learning”, 2013.
N. A. Demerdash, and J. F. Bangura, “Characterization of induction
motors in adjustable-speed drives using a time-stepping coupled finiteelement state-space method including experimental validation”, IEEE T.
Ind. Appl., vol. 35, no. 4, pp. 790-802, 1999.
S. Haltsonen, “An endpoint relaxation method for dynamic time warping
algorithms”, in Proceedings of the IEEE International Conference on
Acoustics, Speech and Signal Processing, 1984, pp. 360-363.
B. Hu, Y. Chen, and E. Keogh, “Time Series Classification under More
Realistic Assumptions”, in Proceedings of the SIAM International
Conference on Data Mining, 2013, pp. 578-586.

M. W. Kadous, “Temporal Classification: Extending the Classification
Paradigm to Multivariate Time Series”, Doctoral Thesis, University of
New South Wales, 2002.
[10] E. Keogh, and C. A. Ratanamahatana, “Exact indexing of dynamic time
warping”, Knowl. Inf. Syst., vol. 7, no. 3, pp. 358-386, 2005.
[11] T. Kiyohara, R. Orihara, Y. Sei, Y. Tahara, and A. Ohsuga, A, “Activity
Recognition for Dogs Based on Time-series Data Analysis”, inProceedings of the International Conference on Agents and Artificial
Intelligence, 2015, pp. 163-184.
[12] D. Maier, “The Complexity of Some Problems on Subsequences andSupersequences”, J. ACM, vol. 25, no. 2, pp. 322-336, 1978.
[13] M. Müller, “Dynamic Time Warping”. Information retrieval for music
and motion. Springer, pp. 69-84, 2007.
[14] C. S. Myers, “A comparative study of several dynamic time warping
algorithms for speech recognition”, Doctoral Thesis, Massachusetts
Institute of Technology, 1980.
[15] R. J. Povinelli, M. T. Johnson, A. C. Lindgren, and J. Ye, “Time seriesclassification using Gaussian mixture models of reconstructed phasespaces”, IEEE T. Knowl. Data. En., vol. 16, no. 6, pp. 779-783, 2004.
[16] L. R. Rabiner, and B. Juang, B., “Pattern-comparison techniques”,
Fundamentals of speech recognition, Prentice-Hall, Inc., pp. 141-241,
1993.
[17] T. Rakthanmanon, B. Campana, A. Mueen, G. E. A. P. A. Batista, B.
Westover, Q. Zhu, J. Zakaria, and E. Keogh. “Searching and mining
trillions of time series subsequences under dynamic time warping”, inProceedings of the ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, 2012, pp. 262-270.
[18] C. A. Ratanamahatana, and E. Keogh, “Three Myths about Dynamic Time
Warping Data Mining”, in Proceedings of the SIAM International
Conference on Data Mining, 2005, pp. 506-510.
[19] U. Rebbapragada, P. Protopapas, C. Brodley, and C. Alcock, “Finding
anomalous periodic time series”, Mach. Learn., vol. 74, no. 3, pp. 281313, 2009.
[20] I. Saini, D. Singh, and A. Khosla, “QRS detection using K-Nearest
neighbor algorithm (KNN) and evaluation on standard ECG databases”,
Journal of Advanced Research, vol. 4, pp. 331–344, 2013.
[21] H. Sakoe, and S. Chiba, “Dynamic Programming Algorithm Optimizationfor Spoken Word Recognition”, IEEE T. Acoust. Speech, vol. 26, no. 1,
pp. 43-49, 1978.
[22] D. F. Silva, G. E. A. P. A. Batista, E. Keogh, “Complementary website
for this work”, 2016, URL http://sites.google.com/site/psidtw/[23] A. Suhrbier, R. Heringer, T. Walther, H. Malberg, and N. Wessel,“Comparison of three methods for beat-to-beat-interval extraction fromcontinuous blood pressure and electrocardiogram with respect to heart
rate variability analysis”, Biomed. Tech., vol. 51, on. 2, pp. 70-76, 2006.
[24] M. Swan, “Sensor Mania! The Internet of Things, Wearable Computing,
Objective Metrics, and the Quantified Self 2.0”, J. Sens. Actuator Netw.,
vol. 1, no. 3, pp. 217-253, 2012.
[25] J. Taborri, E. Palermo, S. Rossi, and P. Cappa, “Gait Partitioning
Methods: A Systematic Review”, Sensors, vol. 16, no. 1, pp. 66, 2016.
[26] P. Tormene, T. Giorgino, S. Quaglini, and M. Stefanelli, “Matching
incomplete time series with dynamic time warping: an algorithm and an
application to post-stroke rehabilitation”, Artif. Intell. Med., vol. 45, no.
1, pp. 11-34, 2009.
[27] K. Ueno, X. Xi, E. Keogh, and D.-J. Lee, “Anytime Classification Using
the Nearest Neighbor Algorithm with Applications to Stream Mining”, inProceedings of the IEEE International Conference on Data Mining, 2006,
pp. 623-632.
[28] D. Vail, and M. Veloso, “Learning from accelerometer data on a legged
robot”, in Proceedings of the IFAC/EURON Symposium on Intelligent
Autonomous Vehicles, 2004.
[29] X. Wang, A. Mueen, H. Ding, G. Trajcevski, P. Scheuermann, and E.
Keogh, “Experimental comparison of representation methods anddistance measures for time series data”, Data Min. Knowl. Discov., vol.
26, no. 2, pp. 275-309, 2013.
[9]