Making the Dynamic Time Warping Distance Warping-Invariant

Computing proximities is a core task for many important time-series mining tasks such as similarity search, nearest-neighbor classification, and clustering. The choice of proximity measure affects the performance of the corresponding proximity-based method. Consequently, a plethora of task-specific proximity measures have been devised [1, 3]. One research direction in time series mining is devoted to constructing data-specific distance functions that can capture some of the data's intrinsic structure. For example, the dynamic time warping (dtw) distance has been devised to account for local variations in speed [39, 31]. Further examples include distances and techniques that account for other variations such as variation in speed, amplitude, offset, endpoints, occlusion, complexity, and mixtures thereof [5]. In some - partly influential - work, the different distances are ascribed as invariant under the respective variation. For example, the dtw-distance is considered as warping-invariant (invariant under variation in speed) [5, 10, 11, 18, 27, 35], the CIDdistance [5] as complexity-invariant, and the ψ-dtw distance [35] as endpoint-invariant.