Date Added: Aug 2012
Many applications generate and consume temporal data and retrieval of time series is a key processing step in many application domains. Dynamic Time Warping (DTW) distance between time series of size N and M is computed relying on a dynamic programming approach which creates and fills an N ? M grid to search for an optimal warp path. Since this can be costly, various heuristics have been proposed to cut away the potentially unproductive portions of the DTW grid. In this paper, the authors argue that time series often carry structural features that can be used for identifying locally relevant constraints to eliminate redundant work.