Abstract
Dynamic Time Warping (DTW) is a wellknown similarity measure for curves, i.e., sequences of points, and especially for time series. We study several proximity problems for curves, where dynamic time warping is the underlying similarity measure. More precisely, we focus on the variants of these problems, in which, whenever we refer to the dynamic time warping distance between two curves, one of them is a line segment (i.e., a sequence of length two). These variants already reveal some of the difficulties that occur when dealing with the more general ones.
Specifically, we study the following three problems: (i) distance oracle: given a curve C in ℝ^d, preprocess it to accommodate distance computations between query segments and C, (ii) segment center: given a set ? of curves in ℝ^d, find a segment s that minimizes the maximum distance between s and a curve in ?, and (iii) segment nearest neighbor: given ?, construct a data structure for segment nearest neighbor queries, i.e., return the curve in ? which is closest to a query segment s. We present solutions to these problems in any constant dimension d ≥ 1, using L_∞ for interpoint distances. We also consider the approximation version of the first problem, using L₁ for interpoint distances. That is, given a lengthm curve C in ℝ^d, we construct a data structure of size O(m log m) that allows one to compute a 2approximation of the distance between a query segment s and C in O(log³ m) time.
Finally, we describe an interesting experimental study that we performed, which is related to the first problem above.
BibTeX  Entry
@InProceedings{aronov_et_al:LIPIcs:2020:12679,
author = {Boris Aronov and Matthew J. Katz and Elad Sulami},
title = {{Dynamic Time WarpingBased Proximity Problems}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {9:19:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12679},
URN = {urn:nbn:de:0030drops126794},
doi = {10.4230/LIPIcs.MFCS.2020.9},
annote = {Keywords: dynamic time warping, distance oracle, clustering, nearestneighbor search}
}
Keywords: 

dynamic time warping, distance oracle, clustering, nearestneighbor search 
Collection: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 
Issue Date: 

2020 
Date of publication: 

18.08.2020 