2
$\begingroup$

For given two lists $[s_1, s_2, ... s_n]$ and $[t_1, t_2, ..., t_m]$

I need to implement DTW algorithm with one extra constraint:

If $s_i$ is matched with $t_j$ then the next element $s_{i+1}$ has to be matched with some $t_{j+k}$ close enough to $t_j$ (i.e. $0 \le k \le W$ for some fixed window size $W$).

This constraint has to hold for each $s_i$.

1) Does there exist $O(nm)$ solution to such problem?

2) If an efficient algorithm does not exist, what would be a good practical solution?

(Note that locality constraint mentioned in the DTW link above is different from the constraint I need).

$\endgroup$
  • $\begingroup$ Is $O(nmW)$ time good enough? Do you consider $W$ a constant? $\endgroup$ – D.W. Jan 6 '17 at 20:55
  • $\begingroup$ $O(nmW)$ is definitely worth considering $\endgroup$ – mercury0114 Jan 6 '17 at 21:04
2
$\begingroup$

There is a $O(nmW)$-time algorithm using dynamic programming. Let $A[i,j] = $ the cost of the best matching of $[s_1,\dots,s_i]$ to $[t_1,\dots,t_j]$ such that $s_i$ is matched to $t_j$. Then

$$A[i,j] = \min\{c(s_i,t_j) + A[i-1,j-k] : k=0,1,\dots,W\}.$$

If you consider $W$ a constant, then you obtain a $O(nm)$-time algorithm.

I don't know if the factor of $W$ can be eliminated.


If $W$ is large, this can be improved to $O(nm \lg W)$ time. The basic primitive we need is:

Given an array $B[1..m]$ and $W$, preprocess $B$ so that we can efficiently answer queries "compute $\min\{B[i],B[i+2],\dots,B[i+W-1]\}$".

Here's how to do that. Assume first for simplicity that $W$ is a power of two. You construct secondary arrays $M_2,M_4,M_8,\dots,M_W$ such that $M_w[i] = \min\{B[i],B[i+1],\dots,B[i+w-1]\}$. You can build them up in $O(m \lg W)$ time, as each $M_{2w}$ can be constructed from $M_w$ in $O(m)$ time. Thus if $W$ is a power of two you can answer subsequent queries in $O(1)$ time per query.

If $W$ isn't a power of two, you can still express the interval $i,i+1,i+2,\dots,i+W-1$ as the union of at most $\lg W$ intervals each of whose width is a power of two. Thus, if $W$ isn't a power of 2, you can answer subsequent queries in $O(\lg W)$ time per query.

Finally, apply this to the original problem. You apply this to each row of $A$, i.e., to $A[i,\cdot]$ for each $i$. Then the recurrence can be computed using a single query, and it takes $O(\lg W)$ time instead of $O(W)$ time to compute the min. You'll need to update the secondary arrays each time you update $A[i,j]$, but this takes only $O(\lg W)$ time per update to $A[i,j]$ (as there are only $\lg W$ secondary arrays to update).

In all, you obtain an algorithm whose running time is $O(nm \lg W)$ and with $O(nm \lg W)$ space usage. (I suspect it's also possible to achieve $O(nm \lg W)$ time and $O(nm)$ space, if necessary, by only storing $M_w[i]$ for values of $i$ that are a multiple of $w$, at the cost of about a 2x increase in running time.)

$\endgroup$
  • $\begingroup$ Haha, thanks for your enthusiasm. This speed is more than enough for me. $\endgroup$ – mercury0114 Jan 7 '17 at 10:00
0
$\begingroup$

Although the accepted answer is correct, an alternative solution also works well in practise, when one is not very strict about the $0 \leq k \leq W$ constraint, but still wants to have the "locality" property:

1) Let $cost[i][j]$ be the minimum cost to align $[s_1, s_2, ... s_i]$ and $[t_1, t_2, ..., t_j]$. We first build $cost$ matrix in $O(nm)$ time using dynamic programming.

2) We find the minimum index $last$ such that $s_n$ could have been aligned with $t_{last}$:

last = m;
// While ignoring extra element in the sequence (t_n) won't make cost worse
while (cost[n][last] >= cost[n][last - 1])
    // We ignore it
    last--;
}
return last;

3) After we know $last$, we find the maximum index $first$ such that $s_1$ could have been aligned with $t_{first}$:

int first = last;
    int i = n - 1;
    while (i > 0) {
        // if to align i-th element with first is not worse that other options  
        if (cost[i - 1][first] + distance(i, first) <= cost[i][first - 1]) {
            // we align it
            i--;
        } else {
            // otherwise we have to use one more point from sequence (t_n)
            first--;
        }
    }
return first;

4) At the end we have found a minimal interval $[t_{first}, ... t_{last}]$ with which the whole sequence $(s_n)$ was aligned. If the length of this interval is not too big (e.g. less than $\frac{3}{2}n)$ we can assume that an alignment satisfying "locality" property has been found.

The nice thing about this approach is that it can be coded in $O(nm)$ time and the code is relatively short.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.