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.ICALP.2017.25
URN: urn:nbn:de:0030-drops-73820
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7382/
Go to the corresponding LIPIcs Volume Portal

Gold, Omer ; Sharir, Micha

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

pdf-format:
LIPIcs-ICALP-2017-25.pdf (0.5 MB)

Abstract

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology, consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in X = R^d are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case d = 1, which is perhaps one of the most used in practice.

In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of n points in R, by presenting deterministic algorithms that run in O( n^2 log log log n / log log n ) time. Our algorithms can be extended to work also for higher dimensional spaces R^d, for any constant d, when the underlying distance-metric dist is polyhedral (e.g., L_1, L_infty).

BibTeX - Entry

@InProceedings{gold_et_al:LIPIcs:2017:7382,
  author =	{Omer Gold and Micha Sharir},
  title =	{{Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7382},
  URN =		{urn:nbn:de:0030-drops-73820},
  doi =		{10.4230/LIPIcs.ICALP.2017.25},
  annote =	{Keywords: Dynamic Time Warping, Geometric Edit Distance, Time Series, Points Matching, Geometric Matching}
}

Keywords: Dynamic Time Warping, Geometric Edit Distance, Time Series, Points Matching, Geometric Matching
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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