Improved LDTW Algorithm Based on the Alternating Matrix and the Evolutionary Chain Tree

Abstract

Dynamic time warping under limited warping path length (LDTW) is a state-of-the-art time series similarity evaluation method. However, it suffers from high space-time complexity, which makes some large-scale series evaluations impossible. In this paper, an alternating matrix with a concise structure is proposed to replace the complex three-dimensional matrix in LDTW and reduce the high complexity. Furthermore, an evolutionary chain tree is proposed to represent the warping paths and ensure an effective retrieval of the optimal one. Experiments using the benchmark platform offered by the University of California-Riverside show that our method uses 1.33% of the space, 82.7% of the time used by LDTW on average, which proves the efficiency of the proposed method.

Keywords

• dynamic time warping
• time series
• similarity evaluation
• warping path
• space-time complexity