## Abstract

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(cn^{2}) , which can be translated to O(n^{2}) 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.

Original language | English |
---|---|

Pages (from-to) | 2581-2596 |

Number of pages | 16 |

Journal | Algorithmica |

Volume | 84 |

Issue number | 9 |

DOIs | |

Publication status | Published - Sept 2022 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics