Dynamic time warping-based proximity problems

Boris Aronov, Matthew J. Katz, Elad Sulami

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Dynamic Time Warping (DTW) is a well-known 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 Rd, preprocess it to accommodate distance computations between query segments and C, (ii) segment center: given a set C of curves in Rd, find a segment s that minimizes the maximum distance between s and a curve in C, and (iii) segment nearest neighbor: given C, construct a data structure for segment nearest neighbor queries, i.e., return the curve in C which is closest to a query segment s. We present solutions to these problems in any constant dimension d ≥ 1, using L∞ for inter-point distances. We also consider the approximation version of the first problem, using L1 for inter-point distances. That is, given a length-m curve C in Rd, we construct a data structure of size O(m log m) that allows one to compute a 2-approximation of the distance between a query segment s and C in O(log3 m) time. Finally, we describe an interesting experimental study that we performed, which is related to the first problem above.

    Original languageEnglish (US)
    Title of host publication45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
    EditorsJavier Esparza, Daniel Kral�, Daniel Kral�
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959771597
    DOIs
    StatePublished - Aug 1 2020
    Event45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 - Prague, Czech Republic
    Duration: Aug 25 2020Aug 26 2020

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume170
    ISSN (Print)1868-8969

    Conference

    Conference45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
    CountryCzech Republic
    CityPrague
    Period8/25/208/26/20

    Keywords

    • Clustering
    • Distance oracle
    • Dynamic time warping
    • Nearest-neighbor search

    ASJC Scopus subject areas

    • Software

    Fingerprint Dive into the research topics of 'Dynamic time warping-based proximity problems'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., Katz, M. J., & Sulami, E. (2020). Dynamic time warping-based proximity problems. In J. Esparza, D. Kral�, & D. Kral� (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 [MFCS-2020-9] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 170). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2020.9