Dynamic time warping

A DTW é implementado por um algoritmo de programação dinâmica. O exemplo a seguir ilustra a implementação da DTW para alinhar duas séries temporais s e t, em que d(x, y) é a distância entre os valores x e y. Especificamente, d(x, y) geralmente é calculado como o quadro da distância euclidiana entre eles, ou seja, d(x, y) = (x-y)².

int DTWDistance(s: array [1..n], t: array [1..m]) {    DTW := array [0..n, 0..m]    for i := 1 to n        DTW[i, 0] := infinity    for i := 1 to m        DTW[0, i] := infinity    DTW[0, 0] := 0    for i := 1 to n        for j := 1 to m            cost := d(s[i], t[j<nowiki>])</nowiki>            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion                                        DTW[i  , j-1],    // deletion                                        DTW[i-1, j-1])    // match    return DTW[n, m]}

Comumente, a DTW é associada a uma janela de restrição.^[1] Basicamente, essa técnica limita a distância no eixo do tempo do alinhamento entre valores das séries temporais sendo comparadas.

Por ser calculado por um algoritmo de programação dinâmica bi-dimensional, o cálculo da DTW tem complexidade ${\displaystyle O(N^{2})}$ . Isso torna seu uso inviável em grandes conjuntos de dados. Por isso, diversas técnicas de indexação específicas para essa medida foram propostas para a tarefa de busca por similaridade, tais como lower bound e early abandoning.^[2] Com essas técnicas, é possível encontrar os vizinhos mais próximos de uma dada subsequência em uma quantidade massiva de séries temporais em poucos segundos utilizando a DTW.^[3] Quando a tarefa em execução não pode ser reduzida à busca por similaridade, as únicas alternativas para acelerar o cálculo da DTW são a poda de etapas do seu algoritmo^[4] ou aproximações da medida de distância.^[5]