Approximating CDTW Distance of Piecewise Algebraic Curves

Curves as input data naturally arise in a variety of fields including finance, seismology, medicine, spatio-temporal data mining, malicious activity detection, and more. A common way to analyze these data sets is to do similarity matching or clustering. The most common metrics used for measuring similarity of curves are Dynamic Time Warping (DTW) and Fr'echet distance. These metrics are sensitive to sampling rate and outliers respectively, and do not yield robust outcomes. Continuous Dynamic Time Warping (CDTW) is a more robust distance metric that improves upon DTW and Fr'echet distances. Existing algorithms for CDTW are either exact algorithms that focus on non-Euclidean norms and piecewise linear curves, or approximation algorithms limited to piecewise linear curves. We present an approximation algorithm for computing the CDTW distance under Euclidean norm between piecewise (higher degree) algebraic curves. That is, we present a fully polynomial-time approximation scheme (FPTAS) of multiplicative error varepsilon, with O left( (m+n)^frac196 (frac1varepsilon)^frac103 log left( frac (m+n) varepsilon2 right) right) complexity, where m and n are the number of pieces of the two input curves.