Kuszmaul, William
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the LowDistance Regime and Approximate Evaluation
Abstract
Dynamic time warping distance (DTW) is a widely used distance measure between time series, with applications in areas such as speech recognition and bioinformatics. The best known algorithms for computing DTW run in near quadratic time, and conditional lower bounds prohibit the existence of significantly faster algorithms.
The lower bounds do not prevent a faster algorithm for the important special case in which the DTW is small, however. For an arbitrary metric space Sigma with distances normalized so that the smallest nonzero distance is one, we present an algorithm which computes dtw(x, y) for two strings x and y over Sigma in time O(n * dtw(x, y)). When dtw(x, y) is small, this represents a significant speedup over the standard quadratictime algorithm.
Using our lowdistance regime algorithm as a building block, we also present an approximation algorithm which computes dtw(x, y) within a factor of O(n^epsilon) in time O~(n^{2  epsilon}) for 0 < epsilon < 1. The algorithm allows for the strings x and y to be taken over an arbitrary wellseparated tree metric with logarithmic depth and at most exponential aspect ratio. Notably, any polynomialsize metric space can be efficiently embedded into such a tree metric with logarithmic expected distortion. Extending our techniques further, we also obtain the first approximation algorithm for edit distance to work with characters taken from an arbitrary metric space, providing an n^epsilonapproximation in time O~(n^{2  epsilon}), with high probability.
Finally, we turn our attention to the relationship between edit distance and dynamic time warping distance. We prove a reduction from computing edit distance over an arbitrary metric space to computing DTW over the same metric space, except with an added null character (whose distance to a letter l is defined to be the editdistance insertion cost of l). Applying our reduction to a conditional lower bound of Bringmann and Künnemann pertaining to edit distance over {0, 1}, we obtain a conditional lower bound for computing DTW over a three letter alphabet (with distances of zero and one). This improves on a previous result of Abboud, Backurs, and Williams, who gave a conditional lower bound for DTW over an alphabet of size five.
With a similar approach, we also prove a reduction from computing edit distance (over generalized Hamming Space) to computing longestcommonsubsequence length (LCS) over an alphabet with an added null character. Surprisingly, this means that one can recover conditional lower bounds for LCS directly from those for edit distance, which was not previously thought to be the case.
BibTeX  Entry
@InProceedings{kuszmaul:LIPIcs:2019:10656,
author = {William Kuszmaul},
title = {{Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the LowDistance Regime and Approximate Evaluation}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {80:180:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10656},
URN = {urn:nbn:de:0030drops106568},
doi = {10.4230/LIPIcs.ICALP.2019.80},
annote = {Keywords: dynamic time warping, edit distance, approximation algorithm, tree metrics}
}
04.07.2019
Keywords: 

dynamic time warping, edit distance, approximation algorithm, tree metrics 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 