Dynamic Time Warping (DTW) is an algorithm for measuring similarity between two temporal sequences that may vary in speed. For instance, similarities in walking could be detected using DTW, even if one person was walking faster than the other. The DTW is used in many application domains, including human motion analysis, speech recognition, or financial data analysis.

The DTW algorithm is based on dynamic programming and its computation is quadratic to the length of its input, which is in many cases quite prohibitive. In 2012, a very interesting paper called “Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping” was published, introducing a number of possible optimizations of the DTW. The paper demonstrated impressive improvement of the DTW efficiency. However, the presented techniques were only used on one-dimensional data and rather basic use-cases.

In the DISA laboratory, we are using the DTW for analyzing motion data, which in their raw format are long high-dimensional time series. We are also able to transform the motions into more compact temporal sequences but with some specific properties. For both these types of time series, it would be extremely useful to have a more efficient implementation of DTW than the basic one we have now. Therefore, the objective of the diploma thesis is to study the techniques presented in the above-mentioned paper and other related ones, and analyze their suitability for our data. The selected techniques will be implemented within the MESSIF library for similarity searching and experimentally evaluated on motion data.