Towards Efficient Interactive Computation of
Dynamic Time Warping Distance

Suppose that an edit operation has been performed at position $j^{*}$ of string $B$ and let $B^{\prime}$ denote the edited string. Let $\mathit{D^{\prime}}$ denote the dynamic programming table for $\mathsf{dtw}(A,B^{\prime})$, and $\mathit{DR^{\prime}}$ the difference representation for $\mathit{D^{\prime}}$. As Figure 4 shows, the number of changed cells in $\mathit{DR^{\prime}}$ can be much smaller than that of changed cells in $\mathit{D^{\prime}}$ (see also Figure 1).

Let $\mathit{DS^{\prime}}$ denote the sparse table for $\mathit{DR^{\prime}}$. Since $\mathit{DS}$ consists only of the boundary cells, the number of changed cells in $\mathit{DS^{\prime}}$ can even be much smaller. In what follows, we show how to efficiently update $\mathit{DS}$ to $\mathit{DS^{\prime}}$.

Because the prefix $B[1..j^{*}-1]$ remains unchanged after the edit operation, for any $j<j^{*}$ we have $\mathit{DR}[i,j]=\mathit{DR^{\prime}}[i,j]$ by Lemma 2 and recurrence (1). Hence, we can restrict ourselves to the indices $j\geq j^{*}$. We define $\ell$ as a correcting offset of string indices before and after the update: $\ell=-1$ if a character has been inserted at position $j^{*}$ of $B$, $\ell=1$ if a character has been deleted from position $j^{*}$ of $B$, and $\ell=0$ otherwise. Now, for any $j\geq j^{*}$, $B^{\prime}[j]=B[j+\ell]$ and column $j$ in $\mathit{DR^{\prime}}$ corresponds to column $j+\ell$ in $\mathit{DR}$.

Let $\mathcal{B}^{I,J}$ be any box on $\mathit{DS^{\prime}}$. For the the top row $i_{\mathrm{T}}^{I}$ of $\mathcal{B}^{I,J}$, we use a linked list $\Delta_{\mathrm{T}}^{I,J}$ that stores the column indices $j$ ($j_{\mathrm{L}}^{J}\leq j\leq j_{\mathrm{R}}^{J}$) such that $\mathit{DS}[i_{\mathrm{T}}^{I},j+\ell]\neq\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},j]$, in increasing order. We also compute, in each element of the list, the value for $\mathit{D^{\prime}}[i_{\mathrm{T}}^{I},j]$ of the corresponding column index $j$. We use similar lists $\Delta_{\mathrm{B}}^{I,J}$, $\Delta_{\mathrm{L}}^{I,J}$, and $\Delta_{\mathrm{R}}^{I,J}$ for the bottom row, left column, and right column of $\mathcal{B}^{I,J}$, respectively. We compute these lists when an edit operation is performed to string $B$, and use them to update $\mathit{DS}$ to $\mathit{DS^{\prime}}$ efficiently.

Let $\#_{\mathrm{chg}}$ denote the number of cells in our sparse representation such that $\mathit{DS}[i+\ell,j]\neq\mathit{DS^{\prime}}[i,j]$. In the sequel, we prove:

Editing string $B$ at position $j^{*}$ incurs some structural changes to $\mathit{DS}$: (a) $\mathcal{B}^{I,J}$ gets wider by one (insertion of the same character to a run), (b) $\mathcal{B}^{I,J}$ gets narrower by one (deletion of a character), (c) $\mathcal{B}^{I,J}$ is divided into $2M$ or $3M$ boxes (insertion of a different character to a run, or character substitution).

In cases (a) and (b), the diagonal links of $\mathcal{B}^{I,J}$ need to be updated. A crucial observation is that the total number of such diagonal links to update is bounded by $m$ for all the $M$ boxes $\mathcal{B}^{1,J}$, …, $\mathcal{B}^{M,J}$, since the destinations of such diagonal links are within the same column of $\mathit{DS^{\prime}}$ ($j_{\mathrm{R}}^{J}+1$ in case (a), and $j_{\mathrm{R}}^{J}-1$ in case (b)). For each box $\mathcal{B}^{I,J}$, if $j_{\mathrm{R}}^{J}-j_{\mathrm{L}}^{J}\geq i_{\mathrm{T}}^{I}-i_{\mathrm{B}}^{I}$ (i.e. $\mathcal{B}^{I,J}$ is a square or a horizontal rectangle), then we scan the top row $i_{\mathrm{T}}^{I}$ from right to left and fix the diagonal links until encountering the first cell in $i_{\mathrm{T}}^{I}$ whose diagonal link needs no updates (see Figure 6). The case with $j_{\mathrm{R}}^{J}-j_{\mathrm{L}}^{J}<i_{\mathrm{T}}^{I}-i_{\mathrm{B}}^{I}$ (i.e. $\mathcal{B}^{I,J}$ is a vertical rectangle) can be treated similarly. By the above observation, these costs for all boxes $\mathcal{B}^{I,J}$ that contain the edit position $j^{*}$ sum up to $O(m)$.

In case (a), we shift the right column $j_{\mathrm{R}}^{J}$ of $\mathit{DS}$ to the right by one position, and reuse it as the right column $j_{\mathrm{R}}^{J}+1$ of $\mathit{DS^{\prime}}$. This incurs two new cells $(i_{\mathrm{T}}^{I},j_{\mathrm{R}}^{J})$ and $(i_{\mathrm{B}}^{I},j_{\mathrm{R}}^{J})$ in $\mathit{DS^{\prime}}$ (the gray cells in Figure 6). We can compute $\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},j_{\mathrm{R}}^{J}]$ in $O(1)$ time using Lemma 2. Now consider to compute $\mathit{DS^{\prime}}[i,j_{\mathrm{R}}^{J}+1]$ for the new right column. Since this right column initially stores $\mathit{DS}[i,j_{\mathrm{R}}^{J}]$ for the old $\mathit{DS}$, using Lemma 2, we can compute $\mathit{DS^{\prime}}[i,j_{\mathrm{R}}^{J}+1]$ in increasing order of $i=1,\ldots,m$, from top to bottom, in $O(1)$ time each. We can compute $\mathit{D^{\prime}}[1,j_{\mathrm{R}}^{J}+1]$ in $O(j_{\mathrm{R}}^{J})$ time by simply scanning the first row. Then, we can compute $\mathit{D^{\prime}}[i,j_{\mathrm{R}}^{J}+1]$ for increasing $i=2,\ldots,m$, using $\mathit{DS^{\prime}}[i,j_{\mathrm{R}}^{J}+1]$, and construct $\Delta_{\mathrm{R}}^{I,J}$. This takes a total of $O(j_{\mathrm{R}}^{J}+m)\subseteq O(m+n)$ time. Finally, $\mathit{DS^{\prime}}[i_{\mathrm{B}}^{I},j_{\mathrm{R}}^{J}]$ is computed from $\mathit{D^{\prime}}[i_{\mathrm{B}}^{I},j_{\mathrm{R}}^{J}+1]$ and $\mathit{DS^{\prime}}[i_{\mathrm{B}}^{I},j_{\mathrm{R}}^{J}+1].L$ in $O(1)$ time. Case (b) can be treated similarly.

For case (c), we consider a sub-case where a character substitution was performed completely inside a run of $B$, at position $j^{*}$. This divides an existing box $\mathcal{B}^{I,J}$ into three boxes $\mathcal{B}^{I,J}$, $\mathcal{B}^{I,J+1}$, and $\mathcal{B}^{I,J+2}$. Thus, there appear three new columns $j^{*}-1$, $j^{*}$, and $j^{*}+1$ in $\mathit{DS^{\prime}}$. Then, the diagonal links for these new columns can be computed in $O(1)$ time each, by scanning row $i_{\mathrm{T}}^{I}$ from $j^{*}+1$, from right to left (see Figure 6). The $\mathit{DS^{\prime}}$ values for the cells in these new columns, as well as the $\mathit{D^{\prime}}$ values for column $j^{*}+1$, can also be computed in similar ways to cases (a) and (b). The other sub-cases of (c) can be treated similarly.

Now our task is to quickly detect the boundary cells $(i,j)$ of $\mathcal{B}^{I,J}$ such that $\mathit{DS}[i,j]\neq\mathit{DS^{\prime}}[i,j]$, and to update them. We assume that the boundary cell values of the preceding boxes $\mathcal{B}^{I-1,J}$ and $\mathcal{B}^{I,J-1}$ have already been computed.

We consider how to detect the cells on the top boundary row $i_{\mathrm{T}}^{I}$ and the cells on the left boundary column $j_{\mathrm{L}}^{J}$ of box $\mathcal{B}^{I,J}$ that need to be updated, and how to update them. For this sake, we use the following lemma on the values of $\mathit{DR}$, which is immediate from Lemma 2:

Intuitively, Lemma 3 states that the cell $(i,j)$ such that $\mathit{DR}[i,j]\neq\mathit{DR^{\prime}}[i,j]$ must be propagated from its left neighbor or its top neighbor. We use this lemma for updating the boundaries of each box $\mathcal{B}^{I,J}$ stored in $\mathit{DS}$. Recall that the values on the preceding row $i_{\mathrm{T}}^{I}-1=i_{\mathrm{B}}^{I-1}$ and on the preceding column $j_{\mathrm{L}}^{J}-1=j_{\mathrm{R}}^{J-1}$ have already been updated. Then, the cells on $i_{\mathrm{T}}^{I}$ and $j_{\mathrm{L}}^{J}$ of box $\mathcal{B}^{I,J}$ with $\mathit{DS}[i,j]\neq\mathit{DS^{\prime}}[i^{\prime},j^{\prime}]$ can be found in constant time each, from the lists $\Delta_{\mathrm{B}}^{I-1,J}$ and $\Delta_{\mathrm{R}}^{I,J-1}$ maintained for the preceding row $i_{\mathrm{T}}^{I}-1=i_{\mathrm{B}}^{I-1}$ and preceding column $j_{\mathrm{L}}^{J}-1=j_{\mathrm{R}}^{J-1}$, respectively.

We process column indices $\Delta_{\mathrm{B}}^{I-1,J}$ in increasing order, and suppose that we are currently processing column index $\hat{j}\in\Delta_{\mathrm{B}}^{I-1,J}$ in the bottom row $i_{\mathrm{B}}^{I-1}$ of the preceding box $\mathcal{B}^{I-1,J}$. According to the above arguments, this indicates that the cells $(i_{\mathrm{T}}^{I},j)$ in the top row $i_{\mathrm{T}}^{I}$ of $\mathcal{B}^{I,J}$ that need to be updated (i.e., $\mathit{DS}[i_{\mathrm{T}}^{I},j]\neq\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},j]$). We assume that, for any $j^{\prime}$ with $j_{\mathrm{L}}^{J}\leq j^{\prime}<\hat{j}$, the value of $\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},j^{\prime}]$ has already been computed. Also, we have maintained a partial list for $\Delta_{\mathrm{T}}^{I,J}$ where the last element of this partial list stores the largest $j^{\prime\prime}$ such that $j_{\mathrm{L}}^{J}\leq j^{\prime\prime}<\hat{j}$ and $\mathit{DS}[i_{\mathrm{T}}^{I},j^{\prime\prime}]\neq\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},j^{\prime\prime}]$, together with the value of $\mathit{D}^{\prime}[i_{\mathrm{T}}^{I},j^{\prime\prime}]$. Now it follows from Lemma 2 that both $\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}].U$ and $\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}].L$ can be respectively computed in constant time from $\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I}-1,\hat{j}].L$ and $\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}-1].U$, and thus we can check whether $\mathit{DS}[i_{\mathrm{T}}^{I},\hat{j}]\neq\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}]$ in constant time as well. In case $\mathit{DS}[i_{\mathrm{T}}^{I},\hat{j}]\neq\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}]$, we append $\hat{j}$ to the partial list for $\Delta_{\mathrm{T}}^{I,J}$. By the definition of $\mathit{DS}$, we have $\mathit{D^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}]=\mathit{D^{\prime}}[i_{\mathrm{T}}^{I}-1,\hat{j}]-\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}].U$. Since $\mathit{D^{\prime}}[i_{\mathrm{T}}^{I}-1,\hat{j}]=\mathit{D^{\prime}}[i_{\mathrm{B}}^{I-1},\hat{j}]$ is stored with the current column index $\hat{j}$ in the list $\Delta_{\mathrm{B}}^{I-1,J}$, $\mathit{D^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}]$ can also be computed in constant time.

Suppose we have processed cell $(i_{\mathrm{T}}^{I},\hat{j})$. We perform the same procedure as above for the right-neighbor cells $(i_{\mathrm{T}}^{I},\hat{j}+p)$ with $p=1$ and increasing $p$, until encountering the first cell $(i_{\mathrm{T}}^{I},\hat{j}+p)$ such that (1) $\mathit{DS}[i_{\mathrm{T}}^{I},\hat{j}+p]=\mathit{DS^{\prime}}[i_{\mathrm{T}}^{I},\hat{j}+p]$, (2) $\hat{j}+p\in\Delta_{\mathrm{B}}^{I-1,J}$, or (3) $\hat{j}+p=j_{\mathrm{R}}^{J}+1$. In cases (1) and (2), we move on to the next element of in $\Delta_{\mathrm{B}}^{I-1,J}$, and perform the same procedure as above. We are done when we encounter case (3) or $\Delta_{\mathrm{B}}^{I-1,J}$ becomes empty. The total number of cells $(i_{\mathrm{T}}^{I},\hat{j}+p)$ for all boxes in $\mathit{DS^{\prime}}$ is bounded by $\#_{\mathrm{chg}}$.

In a similar way, we process row indices $\Delta_{\mathrm{R}}^{I,J-1}$ in increasing order, update the cells on the left column $j_{\mathrm{L}}^{J}$, and maintain another partial list for $\Delta_{\mathrm{L}}^{I,J}$.

The next lemma shows monotonicity on the values of $\mathit{D}$ inside each $\mathcal{B}^{I,J}$.

The next corollary is immediate from Lemma 4.

Now we obtain the next lemma, which is a key to our algorithm.

• Proof. By Corollary 1, $\mathit{DR}[i-1,j].L\geq 0$ and $\mathit{DR}[i,j-1].U\geq 0$ for $i_{\mathrm{T}}^{I}+1<i\leq i_{\mathrm{B}}^{I}$ and $j_{\mathrm{L}}^{J}+1<j\leq j_{\mathrm{R}}^{J}$. Thus clearly $\min\{\mathit{DR}[i-1,j].L,\mathit{DR}[i,j-1].U,0\}=0$. Therefore, for the value of $z$ in Lemma 2, we have $z=(a_{i}-b_{j})^{2}$, which leads to

  	$\displaystyle\mathit{DR}[i,j].U$	$\displaystyle=$	$\displaystyle(a_{i}-b_{j})^{2}-\mathit{DR}[i-1,j].L$		(2)
  	$\displaystyle\mathit{DR}[i,j].L$	$\displaystyle=$	$\displaystyle(a_{i}-b_{j})^{2}-\mathit{DR}[i,j-1].U$		(3)

  By applying equation (3) to the $\mathit{DR}[i-1,j].L$ term of equation (2), we get

  $$\mathit{DR}[i,j].U=(a_{i}-b_{j})^{2}-((a_{i-1}-b_{j})^{2}-\mathit{DR}[i-1,j-1].U).$$

  Recall that $a_{i}=a_{i-1}$, since we are considering cells in the same box $\mathcal{B}^{I,J}$. Thus $\mathit{DR}[i,j].U=\mathit{DR}[i-1,j-1].U$. By applying equation (2) to the $\mathit{DR}[i,j-1].U$ term of equation (3), we similarly obtain $\mathit{DR}[i,j].L=\mathit{DR}[i-1,j-1].L$. $\Box$

For any $i_{\mathrm{T}}^{I}+1<i\leq i_{\mathrm{B}}^{I}$ and $j_{\mathrm{L}}^{J}+1<j\leq j_{\mathrm{R}}^{J}$, let $\ell$ be the smallest positive integer that satisfies $i-\ell=i_{\mathrm{T}}^{I}+1$ or $j-\ell=j_{\mathrm{L}}^{J}+1$. By Lemma 5, for any cell $(i,j)$ on the bottom row $i_{\mathrm{B}}^{I}$ or on the right column $j_{\mathrm{R}}^{J}$, we have $\mathit{DS}[i,j]=\mathit{DR}[i-\ell,j-\ell]$ and $\mathit{DS^{\prime}}[i,j]=\mathit{DR^{\prime}}[i-\ell,j-\ell]$. This means that $\mathit{DS}[i,j]\neq\mathit{DS^{\prime}}[i,j]$ iff $\mathit{DR}[i-\ell,j-\ell]\neq\mathit{DR^{\prime}}[i-\ell,j-\ell]$. Thus, finding cells $(i,j)$ with $\mathit{DS}[i,j]\neq\mathit{DS^{\prime}}[i,j]$ on the bottom row $i_{\mathrm{B}}^{I}$ or on the right column $j_{\mathrm{R}}^{J}$ reduces to finding cells $(i^{\prime},j^{\prime})$ with $\mathit{DR}[i^{\prime},j^{\prime}]\neq\mathit{DR^{\prime}}[i^{\prime},j^{\prime}]$ on the row $i_{\mathrm{T}}^{I}+1$ or on the column $j_{\mathrm{L}}^{J}+1$. See Figure 8.