Breaking out prematurely if a maximum distance is met?

[tommedema]

Thanks for this great little library.

For my purposes I am not interested in a result if a distance is going to be greater than a certain boundary (a maxDistance). For performance reasons I would therefore like to return prematurely if we know that the distance will be greater than this boundary.

I tried to change:

          matrix[ i ][ j ] = cost + distFunc( ser1[ i ], ser2[ j ] );

to:

          matrix[ i ][ j ] = cost + distFunc( ser1[ i ], ser2[ j ] );

          if (matrix[ i ][ j ] > maxDistance) {
            return matrix[ i ][ j ];
          }

But this did not have the desired effect. I'm probably not fully understanding the algorithm. Do you have any pointers that could help?

[tommedema]

I've now implemented this after the end of the inner loop while keeping track of the smallest distance found in the entire range:

export const getDTWDistance = (
  ser1: number[],
  ser2: number[],
  distFunc: (a: number, b: number) => number,
  earlyAbandonBoundary: number
): number => {
  const matrix: number[][] = []
  for (let i = 0; i < ser1.length; i++) {
    matrix[i] = []
    let minDist = Infinity
    for (let j = 0; j < ser2.length; j++) {
      let cost = Infinity
      if (i > 0) {
        cost = Math.min(cost, matrix[i - 1][j])
        if (j > 0) {
          cost = Math.min(cost, matrix[i - 1][j - 1])
          cost = Math.min(cost, matrix[i][j - 1])
        }
      } else {
        if (j > 0) {
          cost = Math.min(cost, matrix[i][j - 1])
        } else {
          cost = 0
        }
      }

      matrix[i][j] = cost + distFunc(ser1[i], ser2[j])
      if (matrix[i][j] < minDist) {
        minDist = matrix[i][j]
      }
    }

    // Note: early abandoning might be further improved
    // See: https://github.com/GordonLesti/dynamic-time-warping/issues/1
    if (minDist > earlyAbandonBoundary) {
      return minDist
    }
  }

  return matrix[ser1.length - 1][ser2.length - 1]
}

This seems to give the desired effect but of course is not as fast as I would like, probably because it has to finish the inner loop first. Is there a reason why the comparison cannot be made inside the inner loop? @GordonLesti