TY - JOUR

T1 - A Faster 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:
© 2022, The Author(s).

PY - 2022

Y1 - 2022

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 length n such that the dissimilarity between any elements is an integer 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(cn2) , which can be translated to O(n2) for constant dissimilarity 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 length n such that the dissimilarity between any elements is an integer 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(cn2) , which can be translated to O(n2) for constant dissimilarity 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 - Dynamic time warping distance

KW - Longest increasing subsequence

KW - Semi-local sequence comparison

KW - String algorithms

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

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

U2 - 10.1007/s00453-022-00968-2

DO - 10.1007/s00453-022-00968-2

M3 - Article

AN - SCOPUS:85129873989

SN - 0178-4617

JO - Algorithmica

JF - Algorithmica

ER -