TY - GEN

T1 - A reduction of the dynamic time warping distance to the longest increasing subsequence length

AU - Sakai, Yoshifumi

AU - Inenaga, Shunsuke

N1 - Funding Information:
The work of Shunsuke Inenaga was supported by JST PRESTO Grant Number JPMJPR1922.
Publisher Copyright:
© Yoshifumi Sakai and Shunsuke Inenaga.

PY - 2020/12

Y1 - 2020/12

N2 - 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(c4n2) or O(c2n2) depending on the variant of the DTW distance used, both of which can be translated to O(n2) 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.

AB - 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(c4n2) or O(c2n2) depending on the variant of the DTW distance used, both of which can be translated to O(n2) 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.

KW - Algorithms

KW - Dynamic time warping distance

KW - Longest increasing subsequence

KW - Semi-local sequence comparison

UR - http://www.scopus.com/inward/record.url?scp=85100947672&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100947672&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2020.6

DO - 10.4230/LIPIcs.ISAAC.2020.6

M3 - Conference contribution

AN - SCOPUS:85100947672

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 61

EP - 616

BT - 31st International Symposium on Algorithms and Computation, ISAAC 2020

A2 - Cao, Yixin

A2 - Cheng, Siu-Wing

A2 - Li, Minming

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st International Symposium on Algorithms and Computation, ISAAC 2020

Y2 - 14 December 2020 through 18 December 2020

ER -