CS Paper Radar

Approximating CDTW Distance of Piecewise Algebraic Curves

Alperen A. Ergür, Shamik Khowala

cs.CG cs.SCmath.OC ·submitted 2026-09-03 13:42 UTC · v1

Abstract

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échet 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échet 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)^{\frac{19}{6}} (\frac{1}{\varepsilon})^{\frac{10}{3}} \log \left( \frac{ (m+n) }{\varepsilon^2} \right) \right)$ complexity, where $m$ and $n$ are the number of pieces of the two input curves.

Comment
24 pages, 5 figures. Preliminary manuscript, comments welcome!

Closest papers

Nearest neighbours by meaning across the whole index.

Constant Approximation of Fréchet Distance in Near-Linear Time

cs.CG ·2026-10-30 ·Haoqiang Huang, Zihe Wang, Shuo Zhang
similarity 0.64
Abstract

We give the first constant-factor approximation for the Fréchet distance in near-linear time. Given two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices, respectively, where $m\le n$, our deterministic algorithm runs in $O(n^{1+\varepsilon})$ time for every fixed $\varepsilon>0$ and $d$, with an approximation factor depending only on $\varepsilon$ and $d$. The same result holds for the discrete Fréchet distance. Our result extends the line of work initiated by Cheng, Huang, and Zhang (STOC 2025) from strongly subquadratic to near-linear time. Our algorithm recursively balances preprocessing and query time. An index for comparing subcurves of a single curve supports faster queries between different curves. We obtain this speedup by replacing one curve with surrogates assembled from indexed subcurves of the other and shared across starting points of matchings. Faster queries then reduce the cost of building the next index. Compact boundary reachability summaries allow the answers to be reused in later recursive calls. After a number of rounds depending only on $\varepsilon$, both preprocessing and query time are near-linear.

0.15

Fine-Grained Hardness of Approximating Dynamic Time Warping

cs.CC cs.DS ·2026-10-06 ·Jihan Wang
theory similarity 0.56
Abstract

We prove conditional lower bounds for approximating dynamic time warping (DTW) over the uniform metric on three symbols. Let $N, M$ be the two string lengths and $n, m$ their respective numbers of runs. Under the Gap Block Disjointness (GBD) hypothesis, for every fixed $κ\in (0,1/6)$ and $δ\in (0,1)$, no deterministic algorithm $N^{κδ}$-approximates DTW on two explicit strings of length $N$ in $O(N^{2-δ})$ time. This matches the known tradeoff between approximation and running-time exponents for deterministic algorithms within any fixed factor greater than six in the approximation exponent. For run-length encoded strings, the Orthogonal Vectors Hypothesis (OVH) rules out any constant-factor approximation in $\widetilde{O}((nm)^{1-δ})$ time for every constant $δ>0$. More generally, for every fixed $η\in (0,1)$, it rules out $(N+M)^{1-η}$-approximation in the same running time. These bounds extend to every fixed metric with at least three points, including absolute distance on $\{0,1,2\}$. Both reductions use long runs to force equal-symbol matches in low-cost alignments. For explicit strings, we combine Boolean gadgets with deterministic gap amplification to obtain a polynomial approximation gap. For run-length encoded strings, an encoding of regular-expression membership gives accepting instances an alignment whose cost does not increase as selected runs grow. Rejecting instances have distance at least the chosen run length, while the number of runs stays fixed.

0.13

Fast Gradient-Based Approximation of Continuous Dynamic Time Warping

cs.LG stat.ML ·2026-10-09 ·Pierre Houedry, Romain Tavenard, Nicolas Courty, Romaric Gaudel
similarity 0.56
Abstract

Dynamic Time Warping (DTW) is a common choice for measuring the discrepancy between time series. It proceeds by finding an optimal warping between timestamps through dynamic programming, which can be slow and is not differentiable. Consequently, several variants have been proposed. Among them, Soft-DTW proposes a smooth formulation of DTW, amenable to gradient computation, while Continuous-DTW (CDTW) introduces a continuous formulation through parametrizable warping functions. Yet, computational costs remain high for both methods and impractical for large datasets in modern machine learning pipelines. This paper revisits CDTW in several ways. After establishing its differentiability under mild conditions, we introduce FastCDTW, which is an efficient approximate solver with two different computational strategies: an exact closed-form scheme for piecewise-linear warping functions, and an unbiased Monte Carlo estimator for smooth ones, such as implicit neural networks. Both strategies provide gradients with respect to the warping function and the input time series, and the resulting algorithm is GPU-friendly. We demonstrate its benefits through its integration into more complex learning problems, including time series averaging, classification and deep domain adaptation.

0.20

WETW: Learning Pair-Specific Weighted Euclidean Distances for Efficient DTW Search

cs.LG cs.AI ·2026-11-12 ·Christos Panourgias, Qitong Wang, George Tzagkarakis, Themis Palpanas
similarity 0.55
Abstract

Dynamic Time Warping (DTW) is the standard distance for similarity search over time series that are misaligned in time, but its cost is quadratic in the series length and lower bounds often prune few candidates, so search over large collections of long series is slow. Learned approximations embed the series to make comparisons cheap, yet compare every pair with the same fixed rule, usually the Euclidean distance, although DTW aligns each pair differently. We observe that, once a pair is aligned, DTW is a Euclidean distance over coordinates selected for that pair. Building on this view, we propose Weighted Euclidean Time Warping (WETW), a learned distance that adapts the comparison of fixed-length embeddings to each pair. A small symmetric network predicts one weight per embedding di- mension and pair without computing an alignment, which halves the error of the best static distance on the same embeddings. The embeddings come from the Weighted Euclidean SEries Encoder (WESEE), whose multi-scale Temporal Feature Extractor keeps the timing information that global pooling removes and raises recall@1 from 0.90 to 0.95, although WETW works with any encoder. We also show that fitting DTW distances is not enough for search, as regression alone misorders the closest neighbours, and that ranking regularization raises recall@1 from 0.79 to 0.95. Our filter-and-verify pipeline, WETW-FV, uses WETW to build a shortlist and exact DTW to check it, so the search is approximate but every returned distance is exact. Over eight datasets, WETW-FV is 11.4x faster than the fastest exact method among the UCR Suite, lower bounds and MESSI-DTW, at a mean recall@10 of 0.93, while the best learned baseline reaches 0.59 at the same speed. On 48K-point series, WETW- FV remains 40x faster than the UCR Suite at a recall@10 of 0.91.

0.21

Dynamic Time Warping in the Low-Distance Regime

cs.DS ·2026-09-30 ·Itai Boneh, Shay Golan, Tomasz Kociumaka
top venuetheory similarity 0.55
Abstract · Accepted to FOCS 2026. Abstract shortened to fit arXiv requirements

Dynamic Time Warping (DTW) is a classical similarity measure for strings and time series that allows local stretching. Given non-empty strings $S,T$ over an alphabet $Σ$ and a cost function $δ:Σ^2\to\mathbb{R}_{\ge0}$, $DTW_δ(S,T)$ is the minimum total cost of equal-length expansions of $S$ and $T$ obtained by duplicating characters. For strings of length at most $n$, DTW is computable in $O(n^2)$ time, and this is conditionally optimal under the Orthogonal Vectors Hypothesis (OVH). We study the low-distance regime, where an integer $k$ upper-bounds $DTW_δ(S,T)$, assuming $δ(a,a)=0$ and $δ(a,b)\ge1$ for $a\ne b$. For several classical similarity measures, this regime admits $O(n+\operatorname{poly}(k))$ algorithms, whereas for DTW with metric costs the best known bound is $O(nk)$. We show that this dependence is essentially optimal: assuming OVH, computing DTW requires $n^{1-o(1)}k$ time even for the discrete mismatch-cost function, which assigns cost $1$ to every mismatch. The lower bound applies to the whole spectrum of thresholds $k$ between constant and linear in $n$. Our reduction from Orthogonal Vectors encodes vector coordinates in the lengths of equal-character runs. The resulting instances are very structured: collapsing runs to single characters reveals long substrings with short periods. We complement the lower bound with a $\tilde O(n+\operatorname{poly}(k))$-time algorithm whenever, after collapsing runs in the inputs, every substring with period $O(k)$ has length $\operatorname{poly}(k)$. Finally, we extend this lower bound to DTW pattern matching, which asks whether any non-empty substring of a length-$n$ text has DTW distance at most $k$ from a length-$m$ pattern. We prove that the classic $O(nm)$-time dynamic-programming algorithm is near-optimal under OVH, even when $k=O(\log n)$.

0.58

Quadratic-Time Barriers from Self-Referential SAT

cs.DS ·2026-11-05 ·Guangyan Zhou
similarity 0.54
Abstract

Under the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit distance on binary strings in $O(n^{2-η})$ time for any fixed $η>0$, where $n$ is the longer sequence length. The same exclusion holds for one-dimensional dynamic time warping on $\{0,1,2,4,8\}$ with absolute-difference cost and for five-symbol dynamic time warping with the discrete metric. We derive Orthogonal Vectors hardness in polylogarithmic dimension by splitting the variables of the logarithmic-width source formula into two halves. Existing sequence reductions have polynomial overhead in the dimension. Their output lengths and construction times allow a fixed saving in the target exponent to yield a fixed proportional saving in the source exponent.

0.21

Computation and Applications of Euclidean and Normed Representations of Massive Data

cs.DS math.OC ·2026-09-06 ·Max Ovsiankin
similarity 0.53
Abstract · PhD dissertation

This thesis investigates Euclidean-space and $\ell_p$-norm representations of different forms of data, with a focus on efficient algorithms for computing these representations in settings where the amount of data is very large. The applications of such representations are also discussed: they may be used to summarize the data in a more compact form for downstream tasks while preserving its most salient properties; and further, they may also be used to extract insights about the data that may not be apparent in its original form. This thesis presents novel algorithms for computing Euclidean representations in the case where the data comes with linear structure, as well as in the case where the data comes only with metric, or distance structure. In addition, we give algorithms for computing $\ell_p$-norm representations in linear structured cases. The analyses of these algorithms use tools from geometry, probability, and optimization, and these tools are used to illuminate other algorithms for similar problems.

0.41

A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics

cs.DS ·2026-09-14 ·Ethan Mader, Borna Tavasoli, Jihan Wang
similarity 0.51
Abstract

We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an $O(n^δ)$-approximation with $\widetilde{O}(n^{2-δ})$ running time for every fixed $0 < δ< 1$. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every $0 < \varepsilon \le 1$, our randomized algorithm runs in $\widetilde{O}(n^{7/4}/\varepsilon^8)$ time and returns a $(3+\varepsilon)$-approximation with probability at least $1-n^{-10}$. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.

0.20