IncDTW Runtime Comparison

Leodolter Maximilian

2019-01-02

Calculation Time Comparison

We split the computation time comparisons by the 3 data analysis tasks: (1) incremental update for new observations, (2) single DTW computation for two time series, and (3) computing the matrix of pairwise DTW distances for a set of time series. To compare the calculation times we use the package microbenchmark. First we define the function cond_mic() to evaluate expressions conditionally to a time constraint. If the evaluation of the former iteration has hit a limit, the next iteration with larger input vectors is truncated. We use this function in all the following runtime experiments.

cond_mic <- function(expr, df, repetitions, threshold, nn){
   if(df[df$expr == expr, "doit"]){
      mic <- microbenchmark::microbenchmark(eval(parse(text = expr)),
                                            times = repetitions)
      mic <- data.frame(expr = expr, times = mic$time,
                        nn=nn, stringsAsFactors = FALSE)
      if(median(mic$time) > threshold){
         df[df$expr == expr, "doit"] <- FALSE
      }
   }else{
      mic <- data.frame(expr = rep(expr, repetitions), times = NA, 
                        nn=nn, stringsAsFactors = FALSE)
   }
   return(list(mic = mic, df = df))
}

Incremental Update of DTW

The fastest way to compute the DTW distance measure is by recycling former calculated results. In the following we simulate the situation of continuously recording new observations and compare the run time for the incremental calculation with a traditional calculation from scratch.

First we define the expressions to be benchmarked and the function cond_mic() we use to test the expressions.

Next we run the for loop and evaluate the expressions for different vector lengths.

Finally we plot the results

Single Computations

To guarantee a fair comparison we set the step pattern equal ‘symmetric1’ (since rucrdtw::ucrdtw_vv() only supports ‘symmetric1’) and do not restrict the warping path. Again first we define the expressions to be benchmarked:

Now we run the computations:

And plot the results:

The only two methods using a vector-based implementations rucrdtw_vec() and IncDTW_vec() are significantly faster than the remaining functions.

Compute a distance matrix

To cluster or classify a set of time series by their pairwise DTW distance measures we need a distance matrix. The function IncDTW::dtw_dismat() helps to get this matrix for a list of univariate or multivariate time series of possibly different lengths. The calculations can be performed single threaded ncores = 1 or multihreaded.

dtw_dismat() is the standard function equivalent to dis_mat() without parallelization. dtw_dismat_3Rcpp() parallels via RcppParallel and dtw_dismat_3R() applies parallel, both with three cores (ncores=3). Except of additional run time costs for initiating the cores these two solutions almost need the same computation time. The function parDist_3() also uses three cores and applies parallelDist::parDist, and takes about 1.8 as long as dis_mat.