Time-series clustering is affected by several factors, such as the characteristics of time-series themselves, the choice of distance or centroid function, etc. In many situations, run-time characteristics are more important, e.g. when the amount of memory is limited by the system, or when excessive running times must be avoided. Most of these aspects cannot be generalized, especially in regards to evaluation of correctness, but things like complexity or growth rate of an algorithm can be assessed relatively more easily. To get an idea of the running times that can be expected for some of the algorithms included in `dtwclust`

, a series of timing experiments were made. Said experiments were not concerned with correctness or accuracy, only with timing characteristics.

These experiments were run using `R`

v3.4.1 and `dtwclust`

v4.0.3. The `microbenchmark`

package (v1.4-2.1) was also used for most of them. The computer used was running GNU/Linux (LTS kernel v4.9) with an `i5-6500`

Intel processor (4 cores) and 16GB of RAM. The whole set of experiments took almost 58 hours to complete. The data used comes from the Character Trajectories set (Lichman 2013), which have different lengths and are originally multivariate series with 3 variables; the univariate versions were extracted from these. All scripts are available online on GitHub. Naturally, since we are dealing with execution times, the experiments cannot be reproduced exactly, but hopefully the median times would not vary too much between systems with similar characteristics.

First we look at the results of the timing experiments for single time-series, i.e., for distances calculated between two individual time-series. The distances tested are those included in the package. Here we look at the effect of window sizes and series’ lengths. Each calculation was repeated 100 times and the *median* value was extracted. An `NA`

window size means that no constraint was used, and note that the vertical scale is different for each facet in the following figure.

The first interesting result relates to the DTW lower bounds: `lb_keogh`

and `lb_improved`

. The window size does not seem to have a very significant effect, and the running time appears to grow linearly with the series’ length for `lb_improved`

. However, `lb_improved`

was faster that `lb_keogh`

. Considering that `lb_improved`

first needs to calculate `lb_keogh`

and then perform additional calculations, this is somewhat puzzling, and the reason is not immediately evident.

The shape-based distance also presents weird behavior. While it was expected that its running time would increase with the series’ length, the bump for the length of 152 is considerably large. It is true that SBD is based on the FFT, and thus it adjusts the input series’ lengths to powers of 2, but if that were the cause, then the bump should have occurred for the series with length of 130, since the next power of 2 for 109 is 128, and it jumps to 256 for a length of 130.

DTW and GAK are the only tested distances that support multivariate series. In the case of DTW, we can see that a window constraint can indeed have a very significant effect on running time, considering that a window size of 10 resulted in a calculation that was 4 times faster than when using no constraint. In this case, using multivariate series (with 3 variables) did not have a very significant effect.

The behavior of GAK was rather surprising. Its running times increase very fast with the series’ length, and neither window size nor number of variables seem to have any effect whatsoever. The normalized version is 3 times slower because it effectively calculates a GAK distance 3 times: one time for `x`

against `y`

, one time for `x`

alone, and one time for `y`

alone; these 3 values are used to calculate the normalized version.

Computing cross-distance matrices for time-series can be optimized in different ways depending on the distance that is used. In the following sections, we look at the way the included distances are optimized, and evaluate the way it affects their running times when doing distance calculations between several time-series.

These experiments were repeated 30 times and the median value was computed, except for the GAK distance which was only repeated 10 times. We look at the effect of several factors: the length of the series, a window size where applicable, the effect of parallelization, and the size of the cross-distance matrix.

First we assess the distances that involve the DTW lower bounds. In the following figure, the `x`

axis contains the total number of cells in the cross-distance matrix, but the color is mapped to the number of *columns* in said matrix. This is relevant in this case because of the envelopes that need to be computed when calculating the lower bounds. These are computed for the series in `y`

, which end up across the columns of the distance matrix. The applied optimization consists in calculating the envelopes for `y`

only once, and re-using them across `x`

. In the case of `dtw_lb`

(which is based on `lb_improved`

), this is also important because nearest neighbors are searched row-wise by default, and more series in `y`

equates to more neighbors to consider. Also note that the `dtw_lb`

calculations make more sense when the series in `x`

and `y`

are different (if the series are the same, the nearest neighbor of a series is always itself, so no iterations take place), which is why there are less data points in those experiments. Given the results of the previous section, the window size value was fixed at 50 for these experiments.

For `lb_keogh`

and `lb_improved`

, we see that the effect of the series’ length is diminished when calculating cross-distance matrices. Parallelization actually seems to be detrimental for these distances, and in the case of sequential calculations (i.e. with one worker), `lb_improved`

was once again slightly faster than `lb_keogh`

. As expected, increasing the number of series in `y`

increases the running times.

The behavior of `dtw_lb`

is more consistent. The length of the series increased the running times of sequential calculations more or less by a constant factor, although this effect disappeared for parallel calculations. Using 2 parallel workers helped quite a bit, but increasing that number to 4 was actually marginally worse. As in the previous case, the number of series in `y`

is directly proportional to the running times.

As mentioned before, the shape-based distance is based on the FFT. Similarly to the DTW lower bounds, the optimization applied here consists in calculating the FFTs only once, although in this case they must be calculated for both `x`

and `y`

. The results are summarized in the next figure.

For sequential calculations, we see here the expected effect of the series’ lengths. Adjusting them to powers of 2 for the FFT meant that the calculations were faster for series of length 109, and for series of length 152 and 196, the times were more or less equal. Parallelization removed this effect somewhat, and helped reduce times slightly, although once again only with 2 parallel workers. This might be different for cross-distance matrices that are much larger.

The DTW distance doesn’t allow for many optimizations. The version implemented in `dtw_basic`

for cross-distance matrices uses less RAM by saving only 2 columns of the local cost matrix (LCM) at all times (since no back-tracking is performed in this case). Moreover, this LCM is only allocated once. The results are shown in the next figure.

The DTW distance presents a much more constant behavior across the board. The difference between univariate and multivariate series is very small, but window sizes and series lengths can have a very significant effect, especially for sequential calculations. Additionally, DTW benefits a lot from parallelization, almost linearly, since using 2 workers reduced times in half, and using 4 workers reduced them practically by a factor of 4. Also note that the growth is very linear, which indicates that DTW cannot be easily optimized much more, something which was already pointed out before (Ratanamahatana and Keogh 2004).

Finally we look at the computations with the GAK distance. As shown in the previous section, this distance is considerably slower, which is why less experiments were made in this section. Moreover, only the normalized version can be used as a *distance* measure (as opposed to a similarity), so only the normalized version was tested.

There are 2 optimizations in place here. As mentioned before, normalization effectively requires calculating a GAK for `x`

and `y`

by themselves, so in order to avoid repeated calculations, these normalization factors are only computed once for cross-distance matrices. GAK also uses a helper matrix to save logarithms during the intermediate calculations, and this matrix is allocated only once.

It is worth pointing out that, in principle, the GAK code is very similar to that of DTW. However, GAK relies on logarithms, whereas DTW only uses arithmetic operations. This means that, unfortunately, GAK probably cannot be optimized much more.

Here we see a much clearer effect of window sizes and series’ lengths and, as was the case for DTW, parallelization can be very beneficial for GAK.

In this section, we briefly look at the running times of 2 centroid functions: shape extraction and DBA. Each experiment was run 50 times and the median value was computed.

Shape extraction is based on SBD, and thus has no window constraints. The multivariate version simply applies the univariate algorithm to each of the variables in the series.

As expected, the multivariate version is proportionally slower than the univariate version. The length of the series can indeed have a significant effect, and using more series naturally increases running times, albeit linearly.

DBA is based on DTW, so it can use window constraints. Additionally, it supports multivariate series for the same reason, but in 2 variations. One variation simply uses the same strategy as shape extraction: it applies the univariate version to each of the variables and binds the resulting series. However, DBA uses the backtracking feature of DTW, and this can be computed based on an LCM calculated from two multivariate series as a whole. In `dtwclust`

, the former variation is the `by-variable`

version, and the latter is the `by-series`

version. Also note that this implementations of DBA allocate the LCM used for backtracking only once; it does not matter if series have different lengths, as long as the LCM’s dimensions are defined based on the longest series.

Both series’ length and window size have a somewhat constant effect on running times. As expected, the `by-series`

multivariate version is more or less as fast as the univariate version, and the `by-variable`

version is proportionally slower. In all cases, however, the growth is linear in the number of series considered.

In this section we look at particular cases of time-series clustering, namely TADPole and some special variations of partitional clustering. Hierarchical is not considered here because its complexity essentially depends on the complexity of the whole cross-distance matrix computation, which was shown indirectly in Section 2.2; this also applies to fuzzy c-medoids. For fuzzy clustering with fuzzy c-means, the whole cross-distance matrix is not computed, but the running times also depend on the distance used, so the results of Section 2.2 are also applicable here.

TADPole is a very particular algorithm. It is mostly limited by RAM, since it requires 3 `N x N`

matrices for `N`

series. It is based on DTW but also requires a cutoff distance (`dc`

) parameter which can directly affect how many DTW calculations are performed. Hence, its run-time behavior cannot be generalized easily. Nevertheless, here we look at its characteristics for the given dataset and a `dc`

value of 10. Each experiment was repeated 30 times and the median value was computed. No parallel tests were made here because the current implementation of TADPole is only parallelized for multiple `dc`

values, and that was not explored.

As expected (from Section 2.2), the choice of DTW lower bound has practically no effect. On the other hand, the choice of window size can have very significant effects. Finally, we can see that the growth is not linear in the number of series.

Even if we were to test only time-series clusterings with the DTW distance, we would have several options to choose from. In this section, we look at the differences between clustering with `dtw_basic`

and `dtw_lb`

when using 2 centroids: partition around medoids (PAM) and DBA. For PAM, we also look briefly at the usage of sparse matrices. These tests were repeated 15 times and the median value was computed.

There are currently 3 different strategies implemented to apply PAM centroids: pre-computing the whole distance matrix once, performing no pre-computation and using a sparse matrix that is updated iteratively, and performing no pre-computation without a sparse matrix. In this section, we briefly look at the differences between the first 2. Even though **the remarks for sparse matrices apply to any distance**, we only use DTW here. The value of `k`

was fixed at 20. For the next figure, only 1 repetition was made in each experiment.

We see above that using `dtw_lb`

can be considerably faster than using `dtw_basic`

, and that using a sparse matrix appears to be the fastest. However, performing only 1 repetition for partitional clustering is a poor choice, and performing more repetitions changes things entirely, as the next figure shows.

Pre-computing the whole distance matrix once means that it can be re-used across all repetitions (left-most facet above), so it makes sense that the running times are practically the same there. As we can see, using `dtw_lb`

is a bad idea even for only 2 repetitions; for more repetitions, the time required is much larger. Using a sparse matrix can indeed be faster, but by the time we make 10 repetitions, the running times are almost the same as when pre-computing the whole matrix. This makes sense, since more repetitions means that there is a higher chance of filling the sparse matrix, and there is an overhead for keeping track of how many cells of the sparse matrix are already set. The next figure shows the percentage of the sparse matrix that was filled for the experiments in the middle facet above.