Memory-restricted multiscale dynamic time warping

Dynamic Time Warping (DTW) is an established method for finding a global alignment between two feature sequences. However, having a computational complexity that is quadratic in the input length, memory consumption becomes a major issue when dealing with long feature sequences. Various strategies have been proposed to reduce the memory requirements of DTW. For example, online alignment approaches often have a constant memory consumption by applying forward path estimation strategies. However, this comes at the cost of robustness. Efficient offline DTW based on multiscale strategies constitutes another approach. While methods built on this principle are usually robust, their memory requirements are still dependent on the input length. By combining ideas from online alignment approaches and offline multiscale strategies, we introduce a novel alignment procedure that allows for specifying a constant upper bound on its memory requirements. This is an important aspect when working on devices with limited computational resources. Experiments show that when restricting the memory consumption of our proposed procedure to eight megabytes, it basically yields the same alignments as the standard DTW procedure.