mlsanityData to 14 Oct 2026

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves

arXiv 2505.23431 ↗First posted 29 May 2025cs.DS cs.CG cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

This paper introduces k-Dynamic Time Warping (k-DTW), a novel dissimilarity measure for polygonal curves. k-DTW has stronger metric properties than Dynamic Time Warping (DTW) and is more robust to outliers than the Fr'echet distance, which are the two gold standards of dissimilarity measures for polygonal curves. We show interesting properties of k-DTW and give an exact algorithm as well as a (1+varepsilon)-approximation algorithm for k-DTW by a parametric search for the k-th largest matched distance. We prove the first dimension-free learning bounds for curves and further learning theoretic results. k-DTW not only admits smaller sample size than DTW for the problem of learning the median of curves, where some factors depending on the curves' complexity m are replaced by k, but we also show a surprising separation on the associated Rademacher and Gaussian complexities: k-DTW admits strictly smaller bounds than DTW, by a factor tildeOmega(√m) when kll m. We complement our theoretical findings with an experimental illustration of the benefits of using k-DTW for clustering and nearest neighbor classification.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 25 of its 60 references that are in the map. First posted on arXiv 29 May 2025.

Builds on

25 of 60 references.

References · 25

  1. 2016Coresets and Sketchescited by 63
  2. 2021Oblivious sketching for logistic regressioncited by 18
  3. 2018Optimal terminal dimensionality reduction in Euclidean spacecited by 11
  4. 2022p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresetscited by 11
  5. 2023Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regressioncited by 8
  6. 2014Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH failscited by 6
  7. 2015Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warpingcited by 6
  8. 2015Clustering time series under the Fr'echet distancecited by 6
  9. 2023Optimal Sketching Bounds for Sparse Linear Regressioncited by 6
  10. 2019Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curvescited by 5
  11. 2020(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warpingcited by 5
  12. 2022Computing Continuous Dynamic Time Warping of Time Series in Polynomial Timecited by 5
13 more
  1. 2019Probabilistic smallest enclosing ball in high dimensions via subgradient samplingcited by 4
  2. 2023On Generalization Bounds for Projective Clusteringcited by 4
  3. 2025A Tight VC-Dimension Analysis of Clustering Coresets with Applicationscited by 4
  4. 2023Solving Proximity Problems for Polygonal Shapes via Polynomialscited by 3
  5. 2024Turnstile ℓp leverage score sampling with applicationscited by 3
  6. 2018Tight Hardness Results for Consensus Problems on Circular Strings and Time Seriescited by 2
  7. 2018SETH Says: Weak Fr'echet Distance is Faster, but only if it is Continuous and in One Dimensioncited by 2
  8. 2019The VC Dimension of Metric Balls under Fr'echet and Hausdorff Distancescited by 2
  9. 2022Random projections for curves in high dimensionscited by 2
  10. 2023Solving Fr'echet Distance Problems by Algebraic Geometric Methodscited by 2
  11. 2023Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warpingcited by 2
  12. 2018Probabilistic embeddings of the Fr'echet distancecited by 1
  13. 2019On the hardness of computing an average curvecited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Hardness of High-Dimensional Linear Classificationcited by 1
  2. 2026Dimension Reduction for Curves: Simplified and Generalizedcited by 0