License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.6
URN: urn:nbn:de:0030-drops-133508
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13350/
Go to the corresponding LIPIcs Volume Portal

Sakai, Yoshifumi ; Inenaga, Shunsuke

A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length

pdf-format:
LIPIcs-ISAAC-2020-6.pdf (0.6 MB)

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 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.

BibTeX - Entry

@InProceedings{sakai_et_al:LIPIcs:2020:13350,
  author =	{Yoshifumi Sakai and Shunsuke Inenaga},
  title =	{{A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13350},
  URN =		{urn:nbn:de:0030-drops-133508},
  doi =		{10.4230/LIPIcs.ISAAC.2020.6},
  annote =	{Keywords: algorithms, dynamic time warping distance, longest increasing subsequence, semi-local sequence comparison}
}

Keywords: algorithms, dynamic time warping distance, longest increasing subsequence, semi-local sequence comparison
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI