Towards Efficient Interactive Computation of Dynamic Time Warping Distance
share
The dynamic time warping (DTW) is a widely-used method that allows us to efficiently compare two time series that can vary in speed. Given two strings A and B of respective lengths m and n, there is a fundamental dynamic programming algorithm that computes the DTW distance for A and B together with an optimal alignment in Θ(mn) time and space. In this paper, we tackle the problem of interactive computation of the DTW distance for dynamic strings, denoted D^2TW, where character-wise edit operation (insertion, deletion, substitution) can be performed at an arbitrary position of the strings. Let M and N be the sizes of the run-length encoding (RLE) of A and B, respectively. We present an algorithm for D^2TW that occupies Θ(mN+nM) space and uses O(m+n+#_chg) ⊆ O(mN + nM) time to update a compact differential representation 𝐷𝑆 of the DP table per edit operation, where #_chg denotes the number of cells in 𝐷𝑆 whose values change after the edit operation. Our method is at least as efficient as the algorithm recently proposed by Froese et al. running in Θ(mN + nM) time, and is faster when #_chg is smaller than O(mN + nM) which, as our preliminary experiments suggest, is likely to be the case in the majority of instances.
READ FULL TEXT