Elastic matching in linear time and constant space

Abstract

Dynamic time warping (DTW) is well known as an effective method for model-based symbol recognition. Unfortunately, its complexity is quadratic in the number of points present in the symbols to be matched. In this paper, we propose a greedy approximate solution to Tappert’s dynamic program formulation of DTW, and show empirically that it performs as well as the exact solution while requiring only linear time to compute.