2026-08-08T00:37:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13350 2024-03-06T10:51:45Z ddc:004 open_access

A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length Sakai, Yoshifumi Inenaga, Shunsuke algorithms dynamic time warping distance longest increasing subsequence semi-local sequence comparison The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of n integers between zero and c, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is O(c⁴ n²) or O(c² n²) depending on the variant of the DTW distance used, both of which can be translated to O(n²) for constant cost functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yoshifumi Sakai and Shunsuke Inenaga 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.6 urn:nbn:de:0030-drops-133508 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.6 eng https://creativecommons.org/licenses/by/3.0/legalcode