runDTW: An Algorithm to Detect Prototypical Patterns in Long Time Series

Subsequence matching and Dynamic Time Warping (DTW) are two well-known research areas in time series analysis. The combination of both concepts in terms of matching time series subsequences via the distance measure DTW is not trivial due to the quadratic runtime complexity of DTW and the typical large number of possible subsequences within one long time series. We propose the algorithm runDTW (to be released with version 1.0.6 of IncDTW on CRAN by end of March 2019) which accelerates the search in a long time series for the k-nearest subsequences of a multivariate time series query pattern by (1) incrementally updating of the normalization and the DTW cost matrix by recycling previous computation results, and by lower bounding and early abandoning to skip and abandon unnecessary computations. We apply runDTW on a database of multivariate accelerometer time series collected via smartphones while travelling with different transport modes. runDTW enables detecting transport mode specific patterns in accelerometer records in acceptable runtime, and provides insight into the transport mode specific data to improve transport mode classification.