IncDTW: An R Package for Incremental Calculation of Dynamic Time Warping

Abstract

Dynamic time warping (DTW) is a popular distance measure for time series analysis and has been applied in many research domains. This paper proposes the R package IncDTW for the incremental calculation of DTW, and based on this principle IncDTW also helps to classify or cluster time series, or perform subsequence matching and k-nearest neighbor search. DTW can measure dissimilarity between two temporal sequences which may vary in speed, with a major downside of high computational costs. Especially for analyzing live data streams, subsequence matching or calculating pairwise distance matrices, runtime intensive computations are unfavorable or can even make the analysis intractable. IncDTW tackles this problem by a vector-based implementation of the DTW algorithm to reduce the space complexity from a quadratic to a linear level in number of observations, and an incremental calculation of DTW for updating interim results to reduce the runtime complexity for online applications. We discuss the fundamental functionalities of IncDTW and apply the package to classify multivariate live stream accelerometer time series for activity recognition. Finally, comparative runtime experiments with various R and Python packages for various data analysis tasks emphasize the broad applicability of IncDTW.

Keywords

• dynamic time warping
• time series
• k-NN
• subsequence matching
• distance measure
• clustering