Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
Authors: Amer Krivošija
Alexander Munteanu
André Nusser
Chris Schwiegelshohn
Venue: ICML 2025 poster (2025)
Keywords: polygonal curves
dynamic time warping
learning theory
clustering
classification
Primary area: theory->learning_theory
TL;DR: We introduce $k$-DTW, a novel distance for polygonal curves that generalizes and provides the best of the gold standards: DTW and Fréchet distances.

Abstract: 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échet 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 $\tilde\Omega(\sqrt{m})$ when $k\ll m$. We complement our theoretical findings with an experimental illustration of the benefits of using $k$-DTW for clustering and nearest neighbor classification.

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
Amer Krivošija' Alexander Munteanu 12
André Nusser
Chris Schwiegelshohn'
Abstract
handwritten characters, can be sampled differently and can therefore look very different at the data level, even though they are similar in content and visual appearance.
This paper introduces k- k-Dynamic Time Warping (k-DTW),, a novel dissimilarity measure for polyg- onal curves. k-DTW has stronger metric proper- ties than Dynamic Time Warping (DTW) and is more robust to outliers than the Fréchet distance, which are the two gold standards of dissimilarity measures for polygonal curves. We show inter- esting properties of k-DTW and give an exact algorithm as well as (1 + -apppoxximation al- gorithm for k-DTW by 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 surpris- ing separation on the associated Rademacher and Gaussian complexities: k-DTW admits strictly smaller bounds than DTW, by a factor (m)m)) when A < m. We complement our theoretical findings with experimental illustration of the benefits of using k-DTW for clustering and near- est neighbor classification.
Dissimilarity measures that involve transformations of one curve into another are therefore studied across the literature. Prominent examples are the Fréchet distance, arguably the most popular measure in computational geometry, or the Dy- namic Time Warping (DTW) distance, which is often used in the context of machine learning. Both can be computed in near-quadratic time in terms of the number of vertices representing the two curves (Alt & Godau, 1995; Eiter & Mannila, 1994; Vintsyuk, 1968). There is also evidence that the Fréchet distance as well as DTW cannot be com- puted in strongly subquadratic time, based on conditional lower bounds that rely on widely accepted complexity theo- retic conjectures (Bringmann, 2014; Bringmann & Mulzer, 2016; Abboud et al., 2015; Bringmann & Künnemann, 2015; Buchin et al., 2019c). Hence, it is widely believed that only small polylogarithmic improvements can be achieved (Agar- wal et al., 2014; Gold & Sharir, 2018) over the quadratic complexity of the natural dynamic programming approach.
Both dissimilarity measures have their caveats: while the Fréchet distance is metric, it is however very sensitive to outlier vertices, to such degree that the existence of a single outlier completely determines the distance. DTW is much less outlier-sensitive but it is not a metric since it does not satisfy the triangle inequality, which can be violated by large factor that depends on the length of the curve. These problems can unfavorably affect the outcome when Fréchet DTW are applied for clustering or classification.
1. Introduction
Handwriting, panel data, time series, sensor-generated tra- jectories, and many more types of data are instances of polygonal curves in Euclidean space. These curves are input for learning processes, both supervised and unsuper- vised. To compare and quantif' the distance of two curves, a suitable dissimilarity measure is needed that reflects the fact that similar curves that represent, for instance, the same
1.1. Our Contributions
We propose novel dissimilarity measure k-DTW that pro- vides the "best of both worlds", while generalizing and interpolating between the Fréchet, and the DTW distance. k-DTW considers only small subset of size k compris- ing the most important part of the transformation between two curves, and ignores the remaining transformation that matches only small deviations, which often correspond to noise. We summarize our main contributions as follows:
'TU Dortmund, Germany University Cologne, Germany Uniivessité Côte d' Azur, CNRS, Inria, France 'Aarhus University, Denmark. Correspondence to: A. Krivošija <amerr kameer.rivosijaee @tuu dortmund.de: de>, A. Munteanu <alexandder.uuttannu munteanu @tu- dortmund.de: de>, A. Nusser <andre ceadteenusserr@oco cnrssfrrrrrr.... C. Schwiegelshohn <cschwiegclshohnGe hathawiieesshhoom@mmaal..mm.. gmail.com>>
1)
We prove that DDDTW provides strengthened triangle inequality compared to DTW and it is thus closer to proper metric, while retaining some robustness of DTW.
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
2) We provide an exact algorithm as well as (1 + s)- approximation algorithm for k-DTW using a parametric search for the k-th largest matched distance with stan- dard DTW on modified distance matrices as a subroutine.
T (Wiy.... Wny) We say that such curve 7 has com- plexity m. For simplicity we write [m] {1, {,,..., .m). In this paper, the distance between two points p, q E R is al- ways their Euclidean distance. Therefore, we write Ip gll to denote their distance under the fn-norm. We work only with discrete transformations, which are based on the fol- lowing notion of traversals.
3) We prove the first dimension-free learning bounds for clustering under k-DTW (including DTW and Fréchet) and a separation result showing that k-DTW has strictly smaller Rademacher and Gaussian complexity than DTW for clustering curves.
(U1...., Uny)) and T (wi,..., Wm") be two curves of complexities m' and m" respectively. Then, traversal T of a and 7 is a sequence that consists of pairs of indices j), which we also call matchings, for vertices 02 E a and wy E T, such that
Let
4) We experimentally show the benefits of k-DTW over the Fréchet distance and DTW for clustering and nearest neighbor classification of synthetic and real world data.
1.2. Other Related Work
i) the traversal T starts with (1, and ends with (m', m"), and
Many dissimilarity measures were introduced to alleviate the drawbacks of the Fréchet distance and DTW. Examples include the weak Fréchet distance (Alt & Godau, 1995) and Continuous Dynamic Time Warping (CDTW) (Buchin, 2007; Buchin et al., 2022). Also, clustering under these measures was considered with different degrees of success. While center based clustering of curves is NP-hard in most cases (Driemel et al., 201 6; Buchin et al., 2019a; 2020; Bulteau et al., 2020), there exist practical approaches to cluster curves under the Fréchet distance (Buchin et al., 2019b) and CDTW (Brankovic et al., 2020).
ii) the pair (i,j) of T can be followed only by one of (i + 1,5). (i.j + +1 or (i 1, + 1).
For simplicity, we write m max(m', mm). Every traver- sal is monotonic by construction, cf. item ii). Let 7 be the set of all traversals T of a and J, then the discrete Fréchet distance between a and r is defined as
dar (o, T) min max ||u; - - TET (iJ))T
which satisfies all axioms of a metric on the set of curves in Euclidean space when we merge any sequence of equal vertices into a single vertex.
We are not aware of previous learning theoretic excess risk bounds for clustering problems on curves. Recent learn- ing bounds in the case of clustering points were given in (Bucarelli et al., 2023). An important concept studied in the context of so-called coresets (Phillips, 2017; Munteanu & Schwiegelshohn, 2018; Munteanu, 2023), is the VC dimension of the space of curves under the Fréchet dis- tance (Driemel et al., 2021; Brüning & Driemel, 2023; Cheng& & Huang, 2024; Cohen-Addad et al., 2025) and dynamic time warping (Conradi et al., 2024). A series of re- sults has been dedicated to dimensionality reducing random projections for curves (Driemel& & Krivošija, 2018; Meintrup et al., 2019; Psarros& & Rohde, 2023).
A related dissimilarity measure of two curves is the dynamic time warping (DTW) distance. It considers the sum of distances matched by the traversal instead of the maximum distance. In the literature we find a generalized version, taking the f--norm for g E [1, oo) of the vector comprising the Euclidean distances matched by the traversal. We denote it the (T distance, which for two curves a and 7 from Rd is defined as
1/9 |0: - wyll
doTwo (a, min
TET
Note that dp (o, 7) can already be computed if we are only given all pair-wise distances between vertices (u, w) with v E a and w E T. Hence, given any dis- tance matrix D E TRm' xm" we define (T
2. Definitions
A curve in Euclidean space Rd, for d E N, is continuous function T: [0, 1] Rd. A polygonal curve is a curve such that there exist finite number m E N of values 0 = t < to <... < fm = 1, with w. = T(4)) which we call vertices. Further, for each E (1...., m - 1} the segment between the two consecutive vertices T (1.) and (4++1) is an affine line segment, i.e., it holds that
(E minrer(Z D99//,))// ( is most popular across the literature, which is the standard DTW distance. Therefore, we simply use DTW to denote D DTW(1) in the remainder.
(T does not satisfy the triangle inequality. However, a relaxed version, depending polynomially on m, holds under certain assumptions, as shown by Lemire (2009):
T(t, +x) (11-))1111 12)
x - ((t)++ 4+1 -t 1()+1)) 1,t1 -
We slightly abuse notation using the functional and the se- quence representation interchangeably for the same curve 7. WWithout this technical assumption, one can define distinct curves with zero distance.
for all x E 10, t0, - tg.. We can thus fully charac- terize a curve T by defining the sequence of its vertices
2

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
Lemma 2.1 (Lemma 3 and Theorem of Lemire (2009)). Given 1 S q < co. There exists no constant e that is in- dependent of the complexities of the input curves such that v) + drrwws (v. 7)). holds for any three curves o, T, and v in Euclidean space g.. If the input curves o, T, and v are of the same complexity m, then it holds that dDtwoo S
T', with the underlying idea that any (i, E T (a, will correspond to some 1i. E v) and (1,j) T(u, r) such that we can use the triangle inequality, We con- struct (a, 7) as follows. For any index 2 of vertex of v, we consider all vertices that it is matched to in the traversals T( v) and T(u, T), i.c., all (f,,)),.... (f.: E T(o, and all (z.ji)....., (x) E Tu, Note that by the def- inition of a traversal, the indices i1, :1.....5 is and ji...... ji are non-empty, contiguous subsets of the natural numbers respectively. W.l.o.g,, let 8 2 t; the other case is symmetric. For all I E (1....,4) (), we add the tuples (it: to our new traversal (" r), and for all I E {t + ,,...,& 8} we add the tuples (e) to T (a, r). Performing this for all indices & of vertices of u, we obtain a valid traversal (1 r).
dDtwoo (O,T) I c. (dDTwoD (o)v)
(dDTwio (a, v) + dprwso(u,
Inspired by the Ky-Fan norm for matrices, which sums their k largest singular values (Fan, 1951), we propose a novel dissimilarity measure for curves, which we call k-largest dynamic time warping distance (k-DTW). It seeks for traversal of the two curves minimizing the sum of the k largest distances between vertices matched by the traversal. We focus on the case k < M, as we want to observe only a small, yet significant part of the transformation between two curves. If & larger than the optimal traversal (whose length is at least m), then we can simply fill the missing part with zeros. We note that this is just for technical convenience.
By construction, we know that any element in (o, was created from some elements in T(o, v) and T(u, r). Fur- thermore, recall that of is the largest distance for some given traversal T. Hence, by the triangle inequality we ob- tain s1 then have
(T,,)) S 81
T(v.r) Using this inequality, we T(a.v) + 81
Definition 2.2 (K-DTW distance). Given two curves (t1...., Um)) ) and 7 (W1..... Wmn) in Euclidean space IR and parameter k E N, let T be the set of all traversals T' of a and 7. Let the pair (i, E T attain the (-th largest distance si 8(2²) ||u. - wey || in T such that 81 2 $2 Z
S Σx ('(o.) S kk. ((,))
dL-rW(OOTT)
T(a,o) + + ((ott))
I ke (5)
(T)
(T)
S k (dk v) + de T)).
2 $|T| (T) where (7) denotes the number of pairs in T. For
At first glance, it might seem that the above inequalities are quite loose. However, we prove in the remainder that they are actually tight in general. To this end, consider the curves o, and v. each of complexity m 2 3, similar to the curves that Lemire (2009) introduced for the proof of Lemma 2. That is, let a = (O..... 0) T = EO, 0) and v = 0,, 0) Let h S m 1a-2 2. Then, d4.rrw (a, r) = k, di-Drw(a, v) = E, and de-nrw(U, r) = O, implying that the relaxed triangle inequality that we showed is tight.
any / >> [T'] let s) (T) 0. Then, the k-DTW distance of o
and 7 is defined as
de-Drw(a, T) = min TET 1=1
The k-DTW distance generalizes both, the discrete Fréchet distance (for k = 1), and the DTW distance (for k large enough, e.g., k 2 2m 1).
Further, towards contradiction suppose that there is con- stant > 0 for which any three curves a,, т, and v satisfy de-nTw(a, r) I e. (du.Drw(a, v) + du dr.rrw(u,,7 r)). Then as- suming k < 2, the above example implies that c 2 k. In the remaining case where l > m 2, the inequality implies de de-nnw(a, = (m 2) E S c E, thus e 2 m 2.
2.1. Triangle inequality
The k-DTW distance satisfies relaxed triangle inequality without assumptions on the curves' complexities, which we prove in the following.
Lemma 2.3. For any three curves a, and v in Euclidean space Rd, it holds that
2.2. Robustness
dr.Drw(a r) S k. (dd.Drw(o, v) de.DI((V,T))
The concept of robustness for curve distance measures can be quantified as follows to support the intuition: given two curves whose matched vertices are at constant distance, say 1, if we move one vertex away to increase the distance by large value A, then the average distance contributed per vertex increases through this modification by (/O(k) for k-DTW, k E [m]. This means that Fréchet is largely dominated by the single outlier, while for k-DTW the in- crease averages out, so that one single large perturbation of order A Rs ek is largely indistinguishable from tiny 8
This bound is light. Further, there is no conslant >> 0 independent of k and the complexity of the curves that sat- isfies dr.Drw(a, T) I c. (dz-DTw(O, u) + du.DTW(U, T)) for any three input curves.
Proof. Let T(a, v) and T(V,T) be traversals that realize de-Drw(a, v) and de,Dw((UT)) 7) respectively. Using these traversals, we construct a (not necessarily optimal) traversal
3

---

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
perturbations of (all) single vertices. To make the claim of robustness more rigorous, we follow the outline of (Lop- uhaä & Rousseeuw, 1991) and extend it towards a notion of robustness for curves with respect to the k-DTW distance (including Fréchet and DTW). To the best of our knowl- edge, such a notion of robustness for curves has not been considered before.
3. Construction Algorithm
Here we show how to efficiently compute the k-DTW dis- tance. We first show in Lemma 3.1 that the k-DTW distance between two curves not equal taking the largest dis- tances from the sum that yields their DTW distance. This precludes the option of directly applying the standard DTW algorithm for the computation of k-DTW. We also show that the length of the traversals may differ significantly (linearly in m)) in both directions, which also precludes using a stan- dard DTW algorithm to even estimate the size of a k-DTW traversal. This indicates that no provable approximation can be obtained in such straightforward manner. The proof can be found in Appendix A.
Given a curve π Pm) in Rd. let (T) be its turve-of-top---mediie i.e., ($1,..., 8m)
where each 8; equals the geometric median restricted to
the top-k distances (Krivosija & Munteanu, 2019; Af- shani & Schwiegelshohn, 2024) of the set (PI.....PPI) }- More formally, for all j E [m]] we define 8, = & E argmin,es= Σmp.: Ilp; - +|l- We note that the argmin may be ambiguous. In that case we may choose an arbitrary but fixed element, i.e., we require that 81 _... Sm- We fi- nally note that Exp- Ip; al| dL-DIW(F, o). It is easy to see that f' (x) is translational equivariant, which means that for any Rd that we add simultaneously to all vertices of curve, it holds that Lm (T + v) Im (TT) + u. We prove this property in Lemma A.9 in the appendix.
Lemma 3.1 (Short version of Lemma A.4). Given an inte- ger m 2 5, it holds for any l with S S 4 that there exist curves and T of complexity m such that d4 (r. T) is not equal to the sum of the largest ls distances contribut- ing to do,w(a,T) Furthermore, the difference between traversal lengths can be linear in the complexity m.
We also stress that the standard dynamic programs for DTW or Fréchet computation cannot be adapted in a direct way to E-DTW (i.e., storing the top k distances seen along each path). The problem is that one can update inductively the cost of current solution in a standard way, but the top k distances cannot be updated to preserve optimality in this way along each path to the end of the dynamic program. Other dynamic programming approaches seem to give only (m²² time algorithms (Garfinkel et al., 2006).
First, we define the breakdown point for tm (x) with respect to k-DTW to be the smallest number S S m of vertices to obtain Ty. which equals π in all but é many vertices that may be arbitrarily corrupted, such that 0g (Te) is also arbitrarily corrupted. Formally, we define B(tms TT ==
minff E [m]] | supx, de.or((m (F), 4m (xe)) = }o).
As a consequence, we need to design new algorithm for the k-DTW distance. Our solution is given in Algorithm I (whose notation we use in the following). It is inspired by Algorithm A of Bertsimas & Sim (2003), designed for the more general framework of top-k-optimization. Our analysis is significantly simplified and adapted to the case of the k-DTW distance. Our algorithm uses the standard DTW subroutine, which can be computed exactly in (m''m" time (Berndt & Clifford, 1994; Vintsyuk, 1968).
We prove the following theorem in Appendix A.3.
Theorem 2.4. Let π = .p......Pm) be a curve with ps E Rd. Let (T) a be the curve-of-top---mmeet -median.. Then 3(tm, n) =
The proof composed of two parts. Lemma A.10 shows 3(m,, TT) S _
If B(1m, т) were larger than k+1 it ver-
implies that any Te that we get by corrupting f = tices would result in bounded (Te) < co. We construct two such corrupted curves, by translating suitable choice of l vertices by = for large vector v. This requires spe- cial care in comparison to (Lopuhaä & Rousseeuw, 1991) to ensure that the set of vertices that determine the top-k distances remains unchanged. The two curves can then be related to each other using the translation equivariance in such a way that the finite bound cannot hold for both simultaneously, thus leading to a contradiction.
We give a self contained proof (in Appendix A) in the k- DTW context, i.e., we prove that Algorithm returns the correct de.DTw (n,,)) T), for any two curves a and T. Theorem 3.2. Given two curves and T, |o] m' and |T| = =m", and parameter k, Algorithm I returns dL-DIW(O,T) in O (m'mm² time, where 2 is the number of distinct distances between any pair of vertices in a and" T.
Here, we give high level intuition of the proof. We show that for an arbitrary (not necessarily optimal) but fixed traver- sal T there exists an iteration where the cost considered by the algorithm equals the k-DTW cost of this traversal T,, i.c., the sum of its k largest distances. In particular this happens in the iteration where the element E[(]] is a correct guess on the smallest element among the l largest distances in T.
Lemma A. shows B(tm, T) 2 k+] If that were not true, then we can show that Lm (me) must be close to the orig- inal ty (T), as otherwise, it would contradict the optimality of ty (m²) for the corrupted curve. Again, the technical de- tails require special care to account for the geometric median of top-k distances instead of the full set of distances.
4

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
Algorithm 1 Computing the k-DTW distance
The first heuristic leverages the fact that the array of distinct distances F[ + 1] is sorted and in iteration I' we have a lower bound of k El("). Whenever this value exceeds the current mincost value, any element E[[] for I < I' is even larger and cannot yield a better solution. Iterations with / < l' can thus be omitted.
1: Input: Curves σ (UI..., ,m)) and T
(Wi,..., (iii...;WW)))) parameter
2: Output: The k-DTW distance de d,,
3: Initialize the distance matrix DII..m', 1..m"] with
D[i,j] < ||0: - -wyl
4: Let array E| + 1] store the distinct distances in
2) For iterations where E|[] is very small, many of the distance entries in D' are larger than zero. This may result in any solution being invalid since it is summing over more than & non-zero elements. We can thus run a binary search for the largest index l' that admits at least one valid solution with no more than i non-zero elements and omit all iterations ( l'.
D including 0 in sorted order E(1] > > E
-[=+ + =
5: Initialize mincost + 00
6: for I {l....,, 1 do
7: /* E[[] represents a current guess on the smallest
element among the largest k distances */
8: D' f max - E[],00 for all (i,j) E [m'] x (m"l
Next, state our rigorous approximation results. The first lemma is simple, yet important ingredient showing that we can use the discrete Fréchet distance (Eiter & Mannila, 1994) as a h-approximation for k-DTW. The proof is given in Appendix A.
9: 1 update best solution by the DTW distance on the
modified D' matrix plus k- E1] */
10:
mincost +- min (mincost, DTW (D') + k. E[]]
11: end for
Lemma 3.3. Given two curves (Vi,..., emy) and == (Wi,-.., Wmmr), and parameter k, it holds that dar(o,T) is a k-approximation for du-orw(a, T), which can be computed in time O mm"). In particular, it holds that daF(a,T) S di-Drw(ar T) S k (a.(T,T).
12: Return: mincost
The reason is that the max in Line 8 of Algorithm 1 evalu- ates to Dii.j] - E[("] for the k largest distances in T while it evaluates to 0 for all other distances in T. Hence, adding k- E[["]] to the cost of traversal T in D' recovers the original cost. In all other iterations the cost cannot become smaller, which can be shown by the following case distinction:
Leveraging Lemma 3.3, we obtain our (1 + =)- approximation result, which quantifies the trade-off between the approximation factor and reducing to logarithmic amount, achieving almost quadratic running time.
For iterations where E[[- < E[t"), we again sum the k largest elements of 7 as, similarly to iteration 1", the max in Line 8 evaluates to D [i .]] ET4 for these elements and is compensated for by adding k E|]. Hence, the cost cannot be less than the k-DTW cost of T, but it can be larger as we potentially sum more elements.
Theorem 3.4. Given two curves a and T, |o| m and
|r| m", and parameter k. there exists (1 + e)- approximation algorithm for k-DTW for any 0 < E S that runs in Om''m'' log(k/s)) time.
The proof is given in Appendix A, and we just provide some intuition here. We first compute the discrete Fréchet distance dap. By Lemma 3.3, this k-approximation for k- DTW allows to round up very small non-zero distances in the distance matrix sddar, which increases the cost by at most k s:dar S -d.-DDW We can also omit iterations &
For iterations I where E[1] > E[T"), some of the k largest elements of T are evaluated to 0 in the max in Line 8. However, by later adding k- E[J], we add at least what we subtracted from Dii.j] j]] in max D(i []] E[1),0 03. Hence, again the sum is least the k-DTW cost of T'
where F![2] > dar, because the cost in iteration is lower bounded by k -E[] k daF 2 di-DTW. The remaining distances in E[1..2] are rounded to their next power of + E. This way, no solution becomes cheaper. At the same time, the cost of any solution can increase by at most a factor of + e, and the number of distinct distances is bounded by
Applying this to the optimal k-DTW traversal T*, we ad- ditionally have that the best solution for suboptimal T cannot ever be smaller than the best and optimal iteration for 7 The minimization in Line 10 thus yields the optimal k-DTW cost. The running time follows from the running time of the standard DTW algorithm repeated for + distinct guesses of the element E[[].
2 E Ollog++ (k/e)) = O(log(k/e)/e))
Note that may become as large as m'm" making the running time quartic in bad cases. We thus introduce two heuristic improvements that effectively reduce the number of iterations that need to be performed on practical instances. This reduces the number of DTW calculations on average by 85% - 97.5% in our experiments in Section
We additionally note that the Fréchet distance cannot be approximated within a factor less than 3 in truly sub- quadratic time unless the Strong Exponential Time Hypothe- sis (SETH) fails (Buchin et al., 2019c). Hence, computing a good approximation for k-DTW has a similar complexity as computing a good approximation for the Fréchet distance.
5

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
4. Dimension-Free and Improved Learning Theory via k-DTW
enough. More specifically, our results imply that k-DTW admits strictly smaller Rademacher and Gaussian complexi- ties than DTW. With this background, we are now ready to state our main learning theoretic results.
We now showcase the benefits of using k-DTW for learn- ing the median of curves. We are given a distribu- tion DD over polygonal curves of complexity m with ver- tices in the unit Euclidean ball By S RR.. We define cost(D, v)) ;= Soa d((a, P)P da. Further, let OPTD := ming cost(D, (D, ()). We call the curve UDD inducing the op- timal objective O D the median curve with respect to D. Given sample P of curves drawn independently and identically distributed from D, we denote by thp := argming cost(P, 3) = argmin, Eoep p d(o, () the empiri- cal risk minimizer. Then the generalization error, or the excess risk of tpp1 is
Theorem 4.1. Let D be an arbitrary distribution curves of complexity m supported over the unit Euclidean ball. Let P be an ii.d. sample from 'D of size [P] = n. Then the Rademacher and Gaussian complexities for learning the median curve of complexity m are bounded above by
m3 min log m, m2 log (mn))
R(P). EO
n
under DTW and
a = cost OPP
mk? min dolog k h² log (mm)
((P).
We are interested in bounding the decrease of E function of the sample size and problem parameters such as the length of the curves, the ambient dimension, or the new k-DTW parameter k.
under k-DTW.
As a direct consequence, the excess risk of th is bounded with constant probability by applying Markov's 's inequal- ity. A high probability bound is possible using a sample complexity of Ó(R(P) + (1og(11/)//r)
common way of bounding the generalization error is by means of bounding the Rademacher and Gaussian complex- ities
see (Bartlett Mendelson, 2002). We complement this by the following lower bounds the Rademacher and Gaussian complexity.
R(P)= == E sup
d(o,, v)
7
Proposition 4.2. Let DD be an arbitrary distribution on curves of complexity m supported over the unit Euclidean ball. Let P be i.idd sample from D of size |P| Then the Rademacher and Gaussian complexities for learn- ing the median curve of complexity m under DTW satisfy RRPP), G(P) E 2 20(mm² /n).
((P) = sup +
i=1 d(oi $9
where r. E {-1, are independent Rademacher random variables and 9i ~ (0, 1) are independent standard Gaus- sians. It is well-known (Bartlet & Mendelson, 2002) for P~ D that there exist absolute constants C1 < C2 such that
The proof in Appendix A is by reduction from the median problem for points. Comparing the upper and lower bounds, we see that (for sufficiently small k) the Rademacher or Gaussian complexity for k-DTW is in D(/m/n)) whereas the corresponding complexity for DTW is in 2i (( mn//n). showing a complexity separation by at least a factor 2 (()m).
EpE S cEEp((P) S (PPP)(P)
Thus, it suffices to bound the Gaussian complexity to get the same bound for the Rademacher complexity and the excess risk well, up to absolute constants.
Before we continue with the main results and their analysis, we would like to point out that the main takeaway message is two-fold: first, to our knowledge, our result gives the first dimension-free bounds for learning clustering of curves, specifically their median, with extensions to p-median to be detailed later. Previous bounds for either DTW (Conradi al., 2024) or Fréchet (Driemel et al., 2021) rely on their respective VC dimension, which is conceptually prone to at least linear dependence on the ambient dimension d. Sec- ond, while the generalization to the novel k-DTW follows in a natural and direct way from our result on DTW, in fact, taking this step together with a lower bound on DTW re- veals non-obvious complexity separation when is small
We first prove generalization bounds with a dependence d. A full proof of the dimension-free bound is given separately in Appendix A. For point set P, we define Vp, D.D to be the set of cost vectors defined by median curves in B with respect to DTW and we define VP.--DWW to be the set of cost vectors defined by median curves in By with respect to k- G-DTW. That is, for any curve C. Bd there exists w with u, = =( v)), o, E P, where d(...) denotes either DTW or k-DTW. Define a net W(Vr, Il- e) as a set of vectors N₂ such that for each & C Bd there exists a vector o' E NVV,, Il-Ilx..) with |o| - u s E for all E [[]]. We start with the following lemma.
6

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
Lemma 4.3. For an absolute constant e, we have that
To bound this quantity, observe that Ei= is distributed as Gaussian g with mean O and its variance sJ = > xim (o/-+1 u//5)² is bounded above by
(v, (1
0 v )g
1) WVVPp (er.D,,,,lbb.r +l) I exp(c- d d- log(m/s))
2) WVVP,,DDT,,llll e)I I exple d m log(k/s)).
Proof. Let e' be a constant depending on e and m, to be determined later. Consider an e'-net with respect to the d-dimensional unit Fuclidean ball, that is a covering of By with Euclidean balls of radius E'. It is well known that such covering C using (1 ) balls exists (Pisier, 1999) and can be represented by the set of centers of each ball. We consider all subsets of centers S S C' of size |S| = m, inducing an approximate curve v/. We claim that for an appropriate choice of e', the cost vectors induced by the curves v define the desired net. The number of these subsets is upper bounded by exp(c dm log(1/=")). Now, we first prove correctness, then reconsider the resulting size. We first observe that for every length curve v there exists t/' such that the jth vertex of 1/ is within distance e' of the jth vertex of v¹ for each j E [m]. by the properties of C. Second, we observe that for any candidate curve a of length at most mn and any traversal T of a and v/, we have for all I E [[T]] that ss 5 where [ is the traversal T applied to and v/ instead of db. Thus, we have that E/n |sT it 2 < 2me'. Since this holds for all traversals, it also holds in particular for the optimal traversal. Thus, setting s' = = e/(2m) implies that |dorw( (o, +)- dorw (o, v/')l S e. Rescaling the net accordingly, we obtain exp(e d m log(m/=)).
O(n . m²)
for j = 0, DTW for j = 0, k-DTW otherwise.
n- --maxx 3)²
O(n k2)
O(n 2 2))
Thus, using the bounds from Lemma 4.3 and letting = m for DTW and = = l for k-DTW, we have that
Σ Esup
1 Σ n2
(o) - -:000)
1
1=ز V /5)log(2 11.11o, 2-11
n
1
Vc. c. d. m x² 22log=
Ve-n- d m 2-25 log =2))
j=1
S c' d m logzz
T(v') $1 S e' by the triangle inequality,
n
where c' are absolute constants. Combining both bounds yields the theorem.
Using a more involved application of the chaining technique, we are able to remove the dependence on d, at the cost of an increased dependence on m and k. Our proof uses terminal embeddings (Narayanan & Nelson, 2019) as a dimensional- ity reduction technique. Subsequently, we construct E-ncts akin to Lemma 4.3 within the reduced dimension that is independent of d. The convergence argument for the infinite chaining series that worked in the case of low d still ap- plies in a similar, yet adapted way to bound all but the first Jmax = Ollo((n) summands. For the remaining terms, we observe that the number of summands is bounded, and each contribution can be bounded again in terms of the net size, which is now independent of d. Unfortunately. the vanishing geometric progression 2-j cancels with size parameters of the s-nets, but the additional factor is only log(2mmax) (1))(11)). which is affordable in our context.
To extend the argument for k-DTW, we merely observe that e' only has to be rescaled by a factor k; yielding the appropriate bound of exp(c- d- m log(k/
D
The nets provided by Lemma 4.3 already allow us to prove the part of Theorem 4.1 that comes with a dependence on d.
Proof of Theorem 4. for low dimensions. We start by in- troducing the so-called chaining technique. Consider an n-dimension vector ni E Vp. Furthermore, let whis E (Vp, 1- 2 be the vector with ||0" -"">">>>>> 1mx S 2- given by Lemma 4.3. Then we may write n as telescop- ing sum with v0.00 = 0
v 1=
Finally. we wish to remark that using standard techniques (e.g. the result by Foster & Rakhlin, 2019), these ideas straightforwardly extend to p-clustering objectives, general- izing p-median to the appropriate problem variant on curves. More specifically, combining our results for the generaliza- tion error and Gaussian complexity for median curves with the main result of Foster & Rakhlin (2019) yields learning rate of Ö(vp- G(P)). In particular, for the special case of m = 1, this recovers the optimal bounds recently proven by Bucarelli et al. (2023) for p p-median clustering of points, up to polylogarithmie factors.
We have due to the triangle inequality G(P)
1
1
Esup
d(o,,
4)9
= Esup
n
i=1
1=1
= Esup
1
(1ghit+1 - -
(u. oh+t! - 29
Esup
i=0
71
7

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
5. Experimental Illustration
Simultaneously, the Fréchet distance suffers from outliers in type-A, curves for = O(1), while k-DTW is sufficiently robust to compensate spikes by summing over O m) distances.
In this section, we conduct experiments using our novel k-DTW dissimilarity measure to understand the effect of the increased robustness compared to the Fréchet distance and the improved relaxed triangle inequality compared to DTW in practice.* To this end, we create a synthetic data set that highlights the properties of the different dissimilarity measures in agglomerative clustering. Subsequently, we perform d-nearest neighbor classification on several real- world data sets.
A Agglomerative Clustering. Since computing a center based clustering for more than one curve is computationally hard even to approximate in most scenarios as already men- tioned in the introduction - we use a popular alternative called Hierarchical Agglomerative Clustering (HAC), which requires only the pairwise distances between the input data points. The partition process starts with each curve being a singleton cluster. The current clusters are then iteratively merged in ascending order of dissimilarity. Given a dis- similarity measure d(a, b) for two eurves, such as Fréchet, DTW, or our novel k-DTW, the dissimilarity of two clus- ters A, B is defined via called linkage functions. The arguably most popular linkage functions are single link- age di [A B) min d(a, b) and complete linkage d(A,, (AA B) = maxag d(a, b), where the distance of two clusters is defined as the minimum resp. maximum dis- tance of two input data points taken from the two clusters (Kaufman & Rousseeuw, 1990).
c+c
Wwwlliow 4+4
www.
Figure/ 1. Curves of type A2 (left); type B (middle); type C' (right)
Synthetic curves. Each of the following curves with ver- tices in IR start and end at O. We define three types of curves of complexity 4m + 1, for any m E N, see Figure I:
A) Curves of type A have "peaks" (outlier vertices), E N. That is, a curve a E Ar consists of
In Figure 2 (top) we see the results for single linkage clus- tering using the three distance measures. DTW (left) clearly has difficulties to distinguish between Ay and type-C curves, since the pairs (Ar, C.) are very close, (Ai, B) are moderately close, while (B, (B) are far from each other, violating the triangle inequality. The Fréchet distance (right) has very large intra-cluster distances between type- A curves that are of the same magnitude the inter-cluster distances. k-DTW (middle) can clearly identify the clusters, as the triangle inequality is less affected, while being ro- bust to the spikes of type-A, curves. As a result, we obtain pure clusters whose intra-cluster distances are reasonably small and clearly distinguished from the large inter-cluster distances. The results for complete linkage are very similar, cf. Figure 2 (bottom).
2m + vertices with value at indices 2i- 1 for
E [2m + 1].
2m - "small value" vertices with value in [0,
at indices 2i for i E [2m], and
peaks of value L., at indices 2i for i E [2m].
The peaks are arbitrarily chosen even indices, cf. Fig-
ure (left).
B) Curves of type B have "large values" between L, L + at all vertices except for the first and the last, cf. Figure (middle). More precisely, a curve 3 E B consists of
2 vertices with value O: B, and Bam+l,
2m 1 vertices with value L at indices 2i + 1 for
all E [2m- 1), and
2m vertices with value in [L, L + e] at indices 2i,
for all i E [2m].
Table I. Performance of the Binary Classification of Curves from the Real-World OULAD Data (Kuzilek et al., 2017), for Fréchet, DTW, and k-DTW.
C) Curves of type C have "small values" for all vertices, cf. Figure (right). More precisely,
2m + 1 vertices with value 0 at indices 2 1 for
Distance
AUC
Accuracy
Fissorr
all E [2m + 1). and
Fréchet
0.73737
0.83742
0.90953
2m "small value" vertices with value in [0, c] at
64-DTW
0.78795
0,85557
0.91796
indices 2i for all E [2m].
72-DTW
0.79639
0.85520
0.91775
76-DTW 0.79772
0,85469
0.91744
We construct 60 curves, 20 of each type, that demonstrate the advantages of the DDD distance by choosing appro- priate values of m, E, 1, and L: the main intuition is that these curves violate the triangle inequality by a ((m) factor for DTW, but only by a k = O(log m.) factor for k-DTW.
DTW
0.78360
0.85459
0.91735
L-Nearest Neighbor Classification. The l-nearest neigh- bor (L-NN) model provides a well-known distance based classifier (Devroye et al., 2013). We use real-world data from the Open University Learning Analytics Dataset
*Our Python code available https: / htt.:/gttthhhh/ggg/ com/ akri vosi 3a/kCTW.
8

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
DTW
k-DTW
FRÉCHET
SINGLE LINKAGE
Tyaed Tyce Moos
Tyank
Tyan
120-
Maad
0.2
0.5
0.0
COMPLETE LINK
1400
1.4
Mindd
Minod
Moad
902
0.0
603
02-
frm nmm In
Figure 2. Single (top) and complete (bottom) linkage clustering; DTW (left), k-DTW (middle), Fréchet distance (right); synthetic data.
(OULAD) (Kuzilek al., 2017) and the datasets from (Aghababa & Phillips, 2023). OULAD provides click- streams of students acting in an online learning management system. We represent n = 275 clickstreams of one course as polygonal curves of complexity m = 294. We use (-NN in order to predict the final exam result, which serves as a binary label indicating 'pass' or 'fail'. See Appendix B.
The results are presented in Appendix B.3.2.
We finally stress that no extensive search for k is needed. In our experience, it suffices to compare k-DTW for few small values & E (In(m), vm, m/10, m//4. At least one k- DTW variant yields best or close to the best performance across all classification performance measures. Simultane- ously, the worst results often attained using one of DTW Fréchet, ef. Tables 7 and 8 in Appendix B. Thus, k-DTW yields the best compromise.
We run 100 times repeated 6-fold cross validation, using 1- NN with a standard choice of [ 17 (ef. Devroye et al., 2013). We perform an exponential search for the best parameter E (2' | E [8]] for the k-DTW distance, and a subsequent finer search. The best results were obtained for & (64, 76), which amounts to roughly 20% 25% of the curves' complexity. A selection of results is given in Table 1. k-DTW outperformed the classification perfor- mance of Fréchet and DTW by margin of up to 8.2% resp. 1.8%, when measured by AUC. k-DTW also shows slight improvements in terms of accuracy and Fi-score. A = 72 provides the best values on average over AUC, accuracy, and -score. Please refer to Table 2 in Appendix B.
Additionally, we perform experiments using several re- lated benchmark distance measures: weak discrete Fréchet distance (Buchin et al., 2019c), edit distance with real penalty (Chen & Ng, 2004). and two variants of partial DTW distance (there are multiple distance measures under the same name in the literature). We use partial window DTW (Sakoe & Chiba, 1978), which matches vertices of each curve only within frame of bounded width w, and par- tial segment DTW (Tak & Hwang, 2007; Luo et al., 2024), which partitions both curves into L segments, each of which are matched via standard DTW.
In addition our explicit parameter search, cross-validated over the full data, we also perform hold-out evaluation. The parameter & is tuned by cross-validation on training data, and the best k is used on hold-out test dataset, for I-NN classification. Specifically, we randomly split the OULAD dataset (Kuzilek et al., 2017) into training and test sets and B, respectively, where the test set comprises 3' 1, or fraction of the input. We find the best value of I on A by running 100 independent repetitions of 6-fold cross-validation, using / V[A for the (-NN training and evaluate it on B. Finally, we compare the performances of Fréchet, k-DTW and DTW distances on the test set B.
We conclude that k-DTW has competitive performance the gold standards DTW and Fréchet, and further baselines. It is mostly among the best performing distance measures, and sometimes outperforms the competitors. It remains an important open problem to obtain better running times for computing the k-DTW distance. In practice, we can speed-up the computation using the DTW heuristic of Silva & Batista (2016). However, solving the challenging prob- lem of improving the top-k optimization framework is an important open question. Its solution would imply prov- ably faster algorithms for k-DTW, as well as for other top- optimization problems.
1

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
Acknowledgements
Berndt, D. J. and Clifford, Using dynamic time warping find patterns in time series. In Proc. of the 3rd Inter- national Conference on Knowledge Discovery and Data Mining. (AAAIWS), pp. 359-370, 1994.
We thank the anonymous reviewers for their valuable com- ments. We thank Felix Krall and Tim Novak for their help with implementations and experiments. Amer Krivošija was supported by the project "From Prediction Agile Interven- tions in the Social Sciences (FAIR)" funded by the Ministry of Culture and Science MKW.NRW, Germany, Alexander Munteanu was supported by the German Research Foun- dation (DFG) grant MU 4662/2-1 (535889065) and by the TU Dortmund Center for Data Science and Simula- tion (DoDaS), and acknowledges additional support by the University of Cologne. André Nusser was supported by the French government through the France 2030 investment plan managed by the National Research Agency (ANR), as part of the Initiative of Excellence of Université Côte Azur under reference number ANR 15-IDEX-01. Chris Schwiegelshohn was partially supported by the Indepen- dent Research Fund Denmark (DFF) under a Sapere Aude Research Leader grant No 1051-00106B.
Bertsimas, D. and Sim, M. Robust discrete optimization and network flows. Math. Program., 98(1-3):49 19144,9711,,01 2003.
Brankovic, M., Buchin, K., Klaren, K., Nusser, A., Popov, A., and Wong, S. (k, 1)-medians clustering of trajectories using continuous dynamic time warping. In Proc. of the 28th ACM International Conference on Advances in Geographic Information Systems, (SIGSPATIAL), pp. 99 110, 2020.
Bringmann, K. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. of the 55th IEEE Symposium Foundations of Computer Science, (FOCS), pp. 661-670, 2014.
Bringmann, K. and Künnemann, M. Quadratic conditional lower bounds for string problems and dynamic time warp- ing. In Proc. the the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 79-97, 2015.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bringmann, K. and Mulzer, W. Approximability of the discrete Fréchet distance. Journal of Computational Ge- ometry, 7(2):46-76, 2016.
References
Brüning, F. and Driemel. A. Simplified and improved bounds the VC-dimension for elastic distance mea- sures. CoRR, abs/2308.0599 05998, 2023.
Abboud, A., Bačkurs, A., and Williams, V. Tight hardness results for LCS and other sequence similarity measures. In Proc. of the 56th IEEE Symposium Foundations of Computer Science, (FOCS), pp. 59-78, 2015.
Bucarelli, M. S., Larsen, M. F,, Schwiegelshohn. C., and Toftrup, M. On generalization bounds for projective clustering. In Advances in Neural Information Processing Systems, (NeurIPS), pp. 71723-71754, 2023.
Afshani, P. and Schwiegelshohn, C. Optimal coresets for low-dimensional geometric median. In International Conference on Machine Learning, (ICMI.), pp. 262-270, 2024.
Buchin, K., Driemel, A., Gudmundsson. J., Horton, M., Kostitsyna, I., Löffler, M., and Struijs, M. Approximating (k, E)-center clustering for curves. In Proc. of the 30th ACM- SMM-SIAMAAA Symposium on Discrete Algorithmss (SODA), pp. 2922-2938, 2019a.
Agarwal, P. K., Ben Avraham, R., Kaplan, H., and Sharir, M. Computing the discrete Fréchet distance subquadratic time. SIAM Journal on Computing, 43(2):429 449, 2014.
Aghababa, H. P. and Phillips. J. M. An experimental study on classifying spatial trajectories. Knowl. Inf. Syst., 65 (4):1587-1609, 2023.
Buchin, K., Driemel, A., van de L'Isle, N., and Nusser, A. kicluster: Center-based clustering of trajectories. In Proc. of the 27th ACM International Conference on Advances in Geographic Information Systems, (SIGSPATIAL), pp. 496 499, 2019b.
Alt, H. and Godau, M. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, -775-91, 1995.
Buchin, K., Ophelders, T., and Speckmann, B. SETH says: Weak Fréchet distance is faster, but only if continuous and in one dimension. In Proc. of the 30th ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 2887 2901, 2019c.
Bartlett, P. L. and Mendelson, S. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463 482, 2002.
10

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
Buchin, K., Driemel, A., and Struijs, M. On the hardness of computing average curve. In Proc. of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, (SWAT), pp. 19:1-19:19, 2020.
Driemel, A., Krivošija, A., and Sohler, C. Clustering time series under the Fréchet distance. In Proc. of the 27th ACM-SIAM Symposium Discrete Algorithms, (SODA), pp. 7766-85,, 2016.
Buchin, K., Nusser, A., and Wong, S. Computing continu- ous dynamic time warping of time series in polynomial time. In Proc. of the 38th International Symposium on Computational Geomelry, (SoCG), pp. 22:1-22:11 2022.
Driemel, A., Nusser, A., Phillips, J. M., and Psarros, The VC dimension of metric balls under Fréchet and Haus- dorff distances. Discrete & Computational Geometry, 66 (4):1351-1381, 2021.
Buchin, M. E. On the Computabilityy of the Frechet Distance Between Triangulated Surfaces. Dissertation, FU Berlin, 2007.
Eiter, T. and Mannila, H. Computing discrete Fréchet dis- tance. Technical Report CD-TR 94/64, Christian Doppler Laboratory, 1994.
Fan, K. Maximum properties and inequalities for the eigen- values of completely continuous operators. Proc. of the National Academy of Sciences, 37(11):760-766, 1951.
Bulteau, L.,, Froese, V., and Niedermeier, R. Tight hardness results for consensus problems on circular strings and time series. SIAM J. Discret. Math., 3483):185--1883, 2020.
Foster, D. J. and Rakhlin, A. too vector contraction for Rademacher complexity. CoRR, abs/1911.06465, 2019.
Chen, L. and Ng, R. T. On the marriage of Ip-norms and edit distance. In Proc. of the 30th International Conference on Very Large Data Bases, (VLDBB), pp. 792-803, 2004.
Garfinkel, R., Feránndez, E., and Lowe, T.J. The k-centrum shortest path problem. Top, 14:279-292 292,, 2006.
Cheng. S. and Huang, H. Solving Fréchet distance problems by algebraic geometric methods. In Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 4502-4515 2024.
Gold, O. and Sharir, M. Dynamic time warping and ge- ometric edit distance: Breaking the quadratic barrier. ACM Trans. Algorithms, 14(4):50:1-50:17, 2018. doi: 10.1145/3230734.
Clarkson, K. L. and Woodruff, D. P. Sketching for M- estimators: A unified approach to robust regression. In Proc. of the 26th Annual -SIM Symposium on Dis- crete Algorithms, (SODA), pp. 921 921-939, 2015.
Kaufman, I., and Rousseeuw, P. J. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley, 1990.
Klein, P. N. and Young, N. E. On the number of iterations for Dantzig-Wolfe optimization and packing-coveric approximation algorithms. SIAM Journal on Computing, 1444):11541117,, 2015.
Cohen-Addad, V. Draganov, A., Russo, M., Saulpic, D., and Schwiegelshohn, C. A tight VC-dimension analysis of clustering coresets with applications. In Proc. the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 4783-4808, 2025.
Krivosija, A. and Munteanu, A. Probabilistic smallest en- closing ball in high dimensions via subgradient sampling. International Symposium on Computational Geometry, (SoCG), pp. 47:1-47:14, 2019.
Conradi, J., Kolbe, B., Psarros, I., and Rohde, D. Fast approximations and coresets for (k, m--ediaa under dy- namic time warping. In 40th International Symposium Computational Geometry, (SoCG), pp. 42:1 12:122 2024.
Kuzilek, J., Hlosta, M., and Zdrahal, Z. Open University Learning Analytics Dataset. Scientific data, 4(1):1-8, 2017. http://dbb.oog//...0088ssaaaaa.
Cruz, M., Macedo, H., Barreto, R., and Guimares, A. GPS Trajectories. UCI Machine Learning Repository, 2016.
Lemire, D. Faster retrieval with a two-pass dynamic-time warping lower bound. Pattern Recognition, 42(9):2169- 2180, 2009.
Devroye, L., Györfi, I.., and Lugosi, G. A probabilistic theory of pattern recognition, volume 31 of Applications of Mathematics Stochastic Modelling and Applied Prob- ability. Springer, 2013.
Lopuhaä, H. P. and Rousseeuw, P. J. Breakdown points of affine equivariant estimators of multivariate location and covariance matrices. The Annals of Statistics, pp. 229-248, 1991.
Driemel, A. and Krivošija, A. Probabilistic embeddings of the Fréchet distance. In Proc. of the 16th Interna- tional Workshop on Approximation and Online Algo- rithms, (WAOA), pp. 218-237, 2018
Luo, Y., Ke, W., Lam, C.-T., and Im, S.-K. An accu- rate slicing method for dynamic time warping algorithm and the segment-level early abandoning optimization. Knowledge Based Systems, 300:1-16, 2024.

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
Mai, T., Munteanu, A., Musco, C., Rao, A., Schwiegelshohn, C., and Woodruff, D. P. Optimal sketching bounds for sparse linear regression. In International Conference on Artificial Intelligence and Statistics, (AISTATS), pp. 11288-11316, 2023.
Sakoe, H. and Chiba, S. Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans- actions on acoustics, speech, and signal processing, 26 (1):43 49, 1978.
Silva, D. F. and Batista, G. Speeding up all- pairwise dynamic time warping matrix calculation. In Proc. of the 2016 SIAM International Conference on Data Mining, (SDM), pp. 837-845. SIAM, 2016.
Meintrup, S., Munteanu, A., and Rohde, D. Random pro- jections and sampling algorithms for clustering of high- dimensional polygonal curves. In Proc. of the 32nd Conference on Neural Information Processing Systems (NeurIPS), pp. 12807-12817, 2019.
Tak, Y.-S. and Hwang, E. A leaf image retrieval scheme based partial dynamic time warping and two-level filtering. In 7th IEEE Conference Computer and In- formation Technology (CTT), pp. 633-638, 2007.
Munteanu, A. Coresets and sketches for regression problems data streams and distributed data. In Machine Learning under Resource Constraints, Volume Fundamentals, pp. 85-98. De Gruyter, Berlin, Boston, 2023.
UIC, Real Trajectory Data. Databases and Mobile Com- puting Laboratory University of Illinois at Chicago, 2006. https//wwww.cs.ucccco wwwp:/ss...cceuubuooeeeeeeeeee wwwp:///w//pp/p/ppp......
Munteanu, A. and Omlor, S. Turnstile Ep leverage score sampling with applications. In 41 International Confer- ence on Machine Learning, (ICML), pp. 36797-36828, 2024.
html.
Vintsyuk, T. Speech discrimination by dynamic program- ming. Cybernetics, 4(1):52-57, 1968.
Munteanu, A. and Schwiegelshohn, C. moresets-methods and history: A theorcticians design pattern for approxi- mation and streaming algorithms. Künstliche Intell., 32 (1):37-53, 2018.
Williams, B. Character Trajectories. UCI Machine Learning
Repository, 2008. https:/4b..og//.3334335C5C7
Munteanu, A., Omlor, S., and Woodruff, D. Oblivious sketching for logistic regression. In Proc. of the 38th International Conference Machine Learning, (ICML), pp. 7861-7871, 2021.
Munteanu, A., Omlor, S., and Peters, C. p-Generalized probit regression and scalable maximum likelihood esti- mation via sketching and coresets. In Proc. of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2073-2100, 2022.
Munteanu, A., Omlor, S., and Woodruff, D. P. Almost linear constant-factor sketching for & and logistic regres- sion. In The / 1thh International Conference on Learning Representations, (ICLR), 2023.
Narayanan, and Nelson, Optimal terminal dimension- ality reduction in euclidean space. In Proc. the 51 ACM Symposium Theory of Computing, (STOC), pp. 2019.
Phillips. J. M. Coresets and sketches. In Handbook of
Discrete and Computational Geometry, pp. 1269-1288.
Chapman and Hal//CRC, 3rd edition, 2017.
Pisier, G. The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics. 94, 1999.
Psarros, I. and Rohde, D. Random projections for curves in high dimensions. In Proc. of the 39th International Symposium on Computational Geometry, (SoCG), pp. 53:1-53:15, 2023.
12

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
A. Proofs
A.I. Algorithmic Part
The discrete Fréchet distance and the (T distance between two curves of complexity m', mz" can be computed using dynamic programming in (m' m") time (Eiter Mannila, 1994; Vintsyuk, 1968; Berndt & Clifford, 1994). Here we show how to efficiently compute the k-DTW distance.
First, prove the correctness and the running time of Algorithm that computes the k-DTW distance of two given curves. Theorem A.1 (Restatement of Theorem 3.2). Given two curves a and T, |o| = m' and |r|= m", and a parameter k, Algorithm/ returns dE.Drw(o, 7) in (m'm"=) time, where & is the number of distinct distances between any pair of vertices in a and T.
Proof of Theorem 3.2/A.1. Consider an arbitrary but fixed traversal T. We prove that there exists an iteration /* where the cost considered by Algorithm equals the exact k-DTW cost of T, i... the sum of the largest & distances in the traversal T, which we denote (T).
Consider iteration | 1- where E is the smallest element that appears in the sum of largest &: elements DTWx (T). Let ky be the number of elements of the matrix D that appear in T such that D > E[I. Note, that in iteration 1" it holds that ki- < k < 41 We note that the margin case where is > [T] implies, similarly to Definition 2.2, that some distances will be filled with zeros. This in turn implies that E[r"] = 0 and thus I" = 2 + is the largest possible index that occurs in Algorithm 1, Therefore the upper bound kz-41 = k2+2 2 is undefined and does not apply in this case.
Further, we have that
cost(T,1") == k. =
Σ
(TF))T
= (k - k..) E[1]+ +
(Di.J-- + E(T") = (T), D(.J)>E
Σ
(J)TT.
since the sum ranges exactly over the k- largest elements and matter how often E(("] appears along T, it is added exactly k - ky- times, i.e., the required number of times to complete the sum of k largest elements, which equals DTW, (T').
Next, we prove that in all other iterations, the considered cost(T, .) cannot be smaller than the actual k-DTW cost DTW To this end, we make a case distinction below. We define Tà C T' to be an arbitrary but fixed subset indexing [7k A largest elements D(c,)) j] in T, where ties are broken arbitrarily. In the margin case that l: > [T], we set Tg = T (the remaining elements are filled with zeros anyway, ef. Definition 2.2). Similarly to the discussion above, k: > [T], no iteration / /* exists, and we can proceed directly with the second case where ( l".
1 1>> 1": Note that for all elements (i.j) E Ta it holds that D(i,j] > E[1, since k 2 k. Then have that
cost(T, = k- E-E[]- +
Σ
max E[1,, 0}
(L.))T
= ETl +
Σ D 0] Σ max -
(1)))
Σ Dli,j] +
max{Dli, - -
DT) +
Σ
max (D(, EyJ. 03 z DT),
since the sum over (1,5) & Tr non-negative
<< I": In this case, we have kr < k and for all (i.j) T% \ Th, it holds that E[] > D]i.j). Thus, the sum is taken over less than & elements, and we have that
cost(T,1) () = l: FE
Σ
max D(i..) F]
(T
13

---

adapt Algorithm to produce (1 approximaaaoo for the Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
(k- - ki) E1 +
E (i.))TT
Di >
D[i, (GJ)ETи
(TW: Σ
Now, we consider an optimal k-DTW traversal T". By the above arguments the cheapest cost for T across all iterations equals the exact k-DTW cost D OPT. We also have that the considered cost for any suboptimal T is never smaller than the actual k-DTW cost (T"). By suboptimality of T', its actual k-DTW cost is strictly larger than the optimal k-DTW cost of T Thus, we have that
min cost(T",,) ,1) (TW)(T")> (TW OPT. [e(++]]
Consequently, the cost returned by Algorithm 1 equals the optimal k-DTW cost of the optimal traversal T", since corresponds to the smallest cost considered in the DTW + k: E[]] minimization across all iterations / + 1].
The running time follows since the initialization can be completed by computing all m'm" pairwise distances D and inserting them into a binary search tree, skipping duplicates. We thus only keep the + distinct items in O mm" log(z)) time and read them in the sorted order in another O(=) time to build the array E. Then, Algorithm runs + S m'm" + 1 iterations and in each iteration it updates distances in the matrix D', which takes time O(''m" m2) and runs one DTW calculation in time 0(m'm"), The final cost update takes only constant time. The total time is thus 0(''m² log(2) 2 + m' m'm" 2) 0(m'm²z)) m)
We next provide quadratic time (1 + =) approximation. As ingredient towards this goal, we first show how to obtain simple a-approximation for k-DTW by calculating the discrete Fréchet distance in quadratic time.
Lemma A.2 (Restatement of Lemma 3.3). Given curves (Ui...., um,! and (Wi,..., Wmn) and parameter k. it holds that dar(o, T) is a k-approximatiin for du-Drw(a, r). which can be computed in time Om'mm") In particular, it holds that dar(a,t) r) & drw((a < k dar(a,
Proof of Lemma 3.3/A.2. Let TF and Tę be traversals of a and r realizing their discrete Fréchet and k-DTW distances, respectively. Using the notation Definition 2.2 we have
k
dar(o,T)=8)) = (Tp)
(Tt)
(Th) de
(TF) < k. (TF) = k- ddda(a,,)) k
1=1
1=1
The running time of (m'mm" for computing dar (o, r) was proven in (Eiter & Mannila, 1994).
Using the k-approximation and rounding of distances, k-DTW distance.
Theorem A.3 (Restatement of Theorem 3.4). Given two curves a and T, |a| m' and |T| m", and a parameter k, there exists a (1 + -aaproxiimatinoonn algorithm for any O < E < 1 that runs in O(m'm' mmmmm log(k/E) time.
Proof of Theorem 3.4/A.3. Let e' =/22. We perform the following modifications of Algorithm
1) We first compute dar(a, which gives k-approximation for de.nrw(o, r) in time O(m'm²" by Lemma 3.3/A.2. Now, set dmii E'dderla.r) and dmax To)
When we build the initial distance matrix D, we round all non-zero distances D[i, with 0 < Dli.5l < dmax to their next higher power of (1 + z')² duin for
i E f..... Josite'
dmax dmiin
log f......
)}
k
Through this modification, the cost of each edge and thus of any traversal cannot decrease. However, increasing the costs induces an additive well multiplicative error, which we bound follows:
14

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
i) The sum of up distances 0 D( amin along any traversal T can only increase by at most
k -mii k. E' dar(o,T) = = (o,
k
since their next power in the progression is (1 11+E") dmin dmin-
ii) Any distance dmin < Dii < dmax can only increase by at most a factor (1 + 5') by construction. By linearity, this also holds for any sum of these distances.
Using these bounds and Lemma 3.3/A.2, the cost of the optimal traversal after rounding the distances is bounded by
(1 + E') de-Drw(o, (0, 7) + é dar (o. r) S (1 + 22') di- 7) = =1 (1+ dr.
2) When we set up the array E|I.. + 1], we can omit all indices / where E[| > dmax = dar (o, T). To see this, recall from the proof of Theorem 3.2/A.1 that the cost of any traversal T in iteration / is lower bounded by k- El[], since we add this amount to sum of further non-negative costs. Using this fact together with Lemma 3.3/A.2 again, the cost of T in iteration l is lower bounded by
k E.E > k- dar (o, 2 de-DTw(aTT),
which implies that the cost of T is not optimal in iteration I.
All modifications can be performed initially in O(m'm") time. Further, E[I..> + 1] contains only E Ologi+e O( log(k/=)) distinct distances. The running time follows by plugging this into the O m²²) running time bound of Theorem 3.2/A.1.
Next, we show that the k-DTW distance between two curves is not equal to taking the largest & distances from the sum that yields their DTW distance. This precludes the option of simply applying the standard DTW algorithm for the computation of k-DTW. We also show that the length of the traversals may differ significantly in both directions, which also precludes using a standard DTW algorithm to estimate the size of k-DTW traversal.
Lemma A.4 (Full version of Lemma 3.1). Given a parameter m E N, it holds that:
i) There exist two curves a and T of complexity m in Euclidean space R&,, such that the difference (Tk--rww>- -TiDrwill of the lengths of the optimal k-DTW and the optimal DTW traversals of a and T, denoted Tx-DDW)) resp. (T(DWW)), is linear in m. It can hold both, (Tk--TW)) < (TDrww) or (T(k-DTW)] > (T(DTW>)-
ii) Assume that m 2 5. Then for any k 1 S k S 4 there exist curves a and T of complexity m. s.1. dEDDT((O T) is not equal to the sum of the largest & distances contributing to dprw (O,
Proof of Lemma 3.1.A.4. We show the first claim of the lemma, that is, that the lengths of the traversals can differ. In the course of the proof, we will also see for the same curves that the value of the k-DTW distance need not equal the sum of the k largest distances in a traversal that witnesses the DTW distance. This will provide the arguments to prove the second statement of the lemma.
For the first inequality [T(k-D < (T(orwyl. let us define K K-gudgets K(I) containing four vertices for each of two 1 I-dimensional curves ((K())) and T(K())) as follows, see Figure (left) for an illustration:
E
35
Uat41 4th L, Uar42 4tL + L
Uut+3 4tL L
U4l+4
4tL + L +
2'
2
2
and
1 4LL,
W4 = 40L
WAr+3 4/L
W4144 4/L + L
2
2'
2
where E N U (0) is the offset, and L, > 0, with = the offset 46 for simplicity):
=
Let the two traversals of (((())) and T(K((1) be (written without 10-
T: (1, (2,2),
15

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
((k-Dww) Roowwl
Ii prwyl Porwwy
L 2
L 2E
U4
U4
V
L
L +
U2
U3
U1
WA
U1
L
2/2
L
W4
L - E
W
L -
W
0
0
W1
W1
W2
-
W2
Figure 3. K-gadget (left); D-gadget (right); traversals realizing k-DTW (bluc); traversals realizing DTW (red).
Te: (1,
holds that [Til < [T2] [Ti] + 1. The traversal T3 realizes the DTW distance, since
Σ
F; w5l = 2L + 2$ > 2L + +2.0+E= Σ
bl wyl= = dorw (o(k)))
(1))
The traversal Ti has the minimum possible traversal size ((7i) = 4), and realizes the k-DTW distance (for E {1, 21, within single gadget), since for these values of ls it holds that drw ( (((()))(((()) table shows that Σt
Σh 2t=1 (Ti), and the following
(ni) Et 1=1 bt
(T2) for k (1,
1 8)
k
k 8
(T))
Σ $ (T)) L+
L
2
(L {) +
3.
L+ L+
(
We note, that for the value à the inequality (TW-DWW>l (TiDwwyl cannot hold (within one gadget) the k-DTWW distance cannot be smaller than the sum of all four distances in the traversal. We discuss this further in the proof of the second claim.
Let m = J. thus m = 4m + r, where 0 S S 3. By concatenating the curves ((K()) and T(K()) from the gadgets (()),, (1),. K(m -1 1) we obtain curves a and т of complexity 4mn. To get the complexity m we can add r vertices at the end of the both curves, each with value 4rhL + L. This does not change the DTW or k-DTW distances of a and r. The traversal obtained by concatenating the traversal T3 repeatedly within each gadget witnesses dprw (o, r), and has length 5m +
Note, that edges of the witness traversals cannot belong to two different gadgets, since any two gadgets are almost 37, apart. More specifically, a pair (i,j) cannot satisfy E (() and wy E k'll + 1) (or E K ([ + 1) and wy K K()) in an optimal traversal for neither DTW nor k-DTW. This is because the entire curves (K()) and T(K(8) are contained in
[4LT. }ec, (4l + 1) ee.. while (k(+1)) and {(((11)) are contained in [4(2 + 1)7. fe, (4(1 + 1) + 1) 33). Thus, a pair (i.j) matching vertices across consecutive gadgets would witness a distance of at least 3L - 2s > 2L 2
Analogously, the traversal obtained by concatenating the traversal Ti repeatedly in the order of the gadgets, witnesses denr((a 7) (for & (1,...,3h)) 3mn)), and has length 4m + r. Therefore, the difference of the traversal lengths
16

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
[T prw)l= Prww m 1. i.e., linear in m, which can be made arbitrarily large. In particular, we conclude that there exist instances for which ((k-DTW)] (T(rr))--
To show that there exist instances for which (Ta-nww) > [T(Dww> we define similar D D-gadgets (tt), containing four vertices for each of two curves ((D())) and T(D(t) as follows, see Figure 3 (right) for an illustration:
E 2'
38
v4t+1 4tI, + T, vart2 = 41T, + I
U4443 411, +
M4444 = 4tT. + I. +
2'
2
and WM++1 = 4th, W = 4th,
W4++3 = 4t + L W4+44 = 4t +
2
where & E N {0} is the offset, and S > 0, with e traversals T1 and T2 as in the first claim. Now, the traversal Ti (with the minimum possible traversal size) realizes the DTW distance, since
L. Let the two traversals of (D()) and T(D(E) be the same Io
E 2 10 - wyy= =2 4e > 2L + (iJ)ETa
Σ
+ = Σ
10-- - wk--lyldaae d (TDD)))
(K.))T
The traversal T2 realizes the k-DTW distance (for h E {1, 4}) within single gadget, since for these values of k it holds that dr. ((D())))(((())) = Σi= 81 and in the following table we see that Et=1 $1 > Σi= 8i for & E {1, 2,,,3344 4).
(Ti)
(T2)
holds
k
Σ 1- 81
(T))
(T2) 81
1
2 (L +
L + L
3 (L + +)+ L 2
L + L + 25
4 (L + () + L+ L + 2E +
As in the first part above, vertices in consecutive gadgets cannot be matched since this would cause more than 2L + 4a cost, which is larger than the whole sum within the gadgets. By concatenating the curves ((D())) and T(D(O) from the gadgets ((0), D.,)...., D(m 1), with additional r vertices 4mL + L at the end of both and т, we obtain curves and t of complexity 4vh + r. The traversal obtained by concatenating the traversal T1 repeatedly for all gadgets, witnesses dDTw (a, r) and has length 4m + r. Analogously, the traversal obtained by concatenating the traversal T2 repeatedly, witnesses de dr.orw( 7) (for
{1..... ........ 4m)) and has length 5m + r. Therefore, the difference of the traversal lengths again [DTx- pTW)l [rw]l r., linear in m, and can be made arbitrarily large. In particular, we conclude that ((l-Drw)| [(DTW)] in this case. This concludes the proof for the first claim of the lemma.
We next prove the second claim of the lemma, first for S k < 3 m and in second step we extend the upper bound. We discuss the cases | < k < 3 3 and 1 < ks < |+] separately. Again, let m = 4m + r. 0 <rsa. 3. 3.
< A S 3 3 J: We can use m. concatenated K- K-gadgets from the first part of the lemma to construct the curves a and r. Both curves are extended at their end by the vertices
U4 = 24mh+2 = U4h433 = W4m++1 = W4mh+2 = W4m+3 = 4m + L.
Hereby, the last (up to) three pairs of vertices (4m + 1, 4m + 1). (4m + 2, 4m + 2) and (4m + 3, 4m 3) in both traversals Ti and T2 do not interfere with the rest of the matchings for the DTW and the k-DTW distance, and do not change the values of d (o, T) and de- T). Then, for all k, s.t. m á < k < 3m 31 2 there will be at least one distance among the largest & distances in the k-DTW traversal from each gadget. Analogously, there will be at most 3 distances among the largest & in the k-DTW traversal. Then, the second claim of the lemma follows from the analysis that we conducted in the first part of the lemma.
1 < k < [T To construct the curves a and in this case, we use k concatenated K K-gadgets from the first part of the lemma, in both curves followed by m - 4k vertices = w, = 4kL + L, for i E {4k + 1,, I...., m). The traversals Ti and T, from the first part of the lemma are extended by the matchings (i, i), E {4k + 1...., Hereby, at least one distance within each of the & gadgets will contribute to the largest &s distances in the kDDTW traversal. The second claim of the lemma thus follows from the analysis of the first claim.
17

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
30
Um-2
Wm
W/
Um
2/3
Um-3
3
W4:
0m-1
W12
Wm-2
01
122
Figure 4, Examplc curves used to prove Lemma A.5. An example instance that has long DTW traversal (length 2m 5) but a short k-DTW traversal (length
The proof of the second claim of the lemma can be repeated analogously using the D-gadgets instead of the K --gadgets. The following cases need to be considered: verbatim. This completes the proof.
k < 4 1 and
< k
< J The rest of the analysis can be conducted
We can even show that the traversal lengths of DTW and k-DTW can be pushed almost to the extremes 2m and m, thus maximizing their difference.
Lemma A.5. There exist two curves a, T of complexity m with vertices R such that the length of the only realizing DTW traversal is 2m 5, and there exists realizing k-DTW traversal of length m for any
Proof of Lemma A.5. We claim that the two curves that realize the properties stated in the lemma are the following, see Figure 4:
σ (U1, 2m) = =(0, -E, 2, ..... 2. 3, 1, 2)
mm
and
T = (W),.... Wm) = (1, -, -1,1 ..... 1, 2, 2),
170
where set 1/10 and choose m large enough, e.g., 2 1000. Recall that the position (i,j) of traversal refers the pair of vertices (v:, w,).
To facilitate the understanding, we first give an informal intuition of the DTW and k-DTW traversals. Thereafter, we continue by giving a rigorous proof. Due to the small e-step in the negative direction at the beginning, a k-DTW traversal is forced to step forward in both curves since it cannot afford a single matching of cost + e. Consequently, the k-DTW traversal needs to continue via the vertices W3 Wm-3 in order to match the vertices v3..... ; Um which can be accomplished in a parallel fashion. The traversal can then be completed using only matchings of cost at most Hence, k-DTW cost and it can be realized by almost parallel traversal of length m 1. For DTW the other hand, leverage that w.....; Wm can be matched Um 2, Um-1; 1, Um with cost of only e² Hence, we match UI,... Um-3 to W1, W2 with cost of m 3 + 2s and then transition into the position (m 2, 3) to match the remainder with cost of e If we step forward earlier on т, then either the matching to U3...., Um or the matching of vertices Wm 2, Wm Wm and Um-2, Um-1, 2m at the end becomes too expensive.
e² is the optimal
We show the claims for DTW and k-D separately, starting with the latter.
18

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
k-DTW: Let S 3. We first show upper bound of k + + the k-DTW cost, which is simply given by the following traversal of a and
(1,1), ..., (m
3, m 3), (m 3, m 2), (m 2, m 1), (m 1, m)) (m, m).
The only matching cost larger than is induced by matching vy and wa with cost of + s², Note that this traversal has length + 1.
To show that this upper bound is tight, we first show the following claim: Consider any traversal and the first time that it reaches Um-3- 3- The sum of the k largest matchings of any such partial traversal is at least k + E².
First, note that the only w E T that have distance wW -o] < 1 for any U E {VI,...,, mm are Wm-11 Wms and we for which only |0j w < 1. Note that Vi and w2 are only matched a traversal that starts with (1, 1), (1, but then any traversal of sufficiently low cost needs to continue with (2. Hence, going directly from (1, (2.2) always better. The only way continue the traversal from here is continue the parallel traversal, as otherwise
would incur matching cost of
more than 1 + e² or multiple costs of + which both are prohibitive for k-DTW cost of + s², It follows from the above observations that any matching to U1,.... Um-3 will lead to k-DTW cost that is at least k - e². This establishes lower bound of & =² on the k-DTW cost, which matches the upper bound.
DTW: We first show that the DTW cost is at most m - 3 + 28 + +2 and this is realized by traversal of length 2m 5. The following traversal of a and T has these properties:
(m - 4, 1) (m 3,2), (m - 2, 2) (m - 1,4)..... (m 1,m- - 2), (m, m 1), (m, m).
(m
We now proceed with proving that the DTW cost is also at least m 3 3 28 + + and is only realized by the above or a longer traversal. Consider which prefixes of J can be matched to V1, Um-3 with a cost that does not exceed C m 3 + 2e + c2. To this end, first note that completing a traversal from any position (m 1m-3, 3, I), with / 2 4, has cost least 2, while any matching of the prefixes 01...., Um-3 and W1, .... wi has least m 3 pairs at distance least 1. C for choice of m and e. Hence, we have match one of the vertices W1, W2, W3 3m As W2 and Wa have distance + E, resp. + =², to U3...... ..., mm-3, matching them to any subsequence of ......, Um-3 of size larger than 1/3g leads to a total matching cost larger than C. Thus, any possible traversal that has cost at most C' necessarily matches the majority of 0g
Thus, the total cost would be at least
Um- to w1. the position (m - 3, 1) would be part of such a traversal, then all pairs 1). E [m - 33.. and the pair (m - 3, 2) would have to be in the traversal as well, which again has cost more than C. Therefore, the position (m - 3, 2) must belong to the traversal, causing the cost + e. But adding even one additional position (1, 2). where I E [3.m m - -4]. into the traversal causes total cost larger than C. Hence, the only remaining traversal with cost of at most C m Equation (1).
2s + 2 is the one that realizes the upper bound given in
19

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
A.2. Learning Theory
Using more involved application of the chaining technique, we are able reduce the dependence on d, at the cost of an increased dependence on and k. To this end, require terminal embeddings defined as follows.
Definition A.6 (Terminal Embeddings). For point set P C R an e-terminal embedding a mapping RR R such that for all P and all q IRd
(1- Uله - (1(())) f())ll (1 + +))pp g/|-
Terminal embeddings are similar to Bahhnson-Lindnsstrusss type embeddings, albeit stronger in the sense that q can be any point in TRd, rather than just applying pairwise distances. Nevertheless, the target dimensions of Johnson-I Oohnson-Lindensrrauss Lindenstrauss
embeddings and terminal embeddings are essentially identical, as proven by Narayanan & Nelson (2019) and summarized in the following lemma.
Lemma A.7. There exist terminal embeddings of target dimension h O(= log PP).
An immediate consequence of the terminal embedding guarantee is that both DTW and k-DTW are preserved up (1 + e) factors, if the target dimension is in O( log(mn)) In the following, show that they also yield alternative bound on the net size for median curves.
Lemma A.8. For absolute constant have that
WWVr, I1-llo,: exp(e m² (ongem//))) E-2)
and
W(VP,.DTW 11.1bo:: e)1 S exp(e k2 log log (mnk//) 2)
Proof. Let = m for DTW and i for k-DTW. We first apply terminal embedding of target dimension h 0(22... e log(mn)).. which preserves DTW and k-DTW up to (1 + e/2) factors, and hence both up to additive error of all the points on the curves are assumed to have most unit Euclidean norm. Subsequently, we apply Lemma 4.3, yielding 25-nets of size
[V(Vp.rrw Il-lo,, =)] s exple- m log
and
k
(VVVA.DTW,Il-ba.t S exp(c h log Inserting the appropriate bounds for and rescaling : yields the claim.
With this lemma, we now give the dimension-free bound on the Rademacher and Gaussian complexity claimed in Theo- rem 4.1.
Proof Theorem 4.1 for high dimensions. As with the proof of the low-dimensional case, we rely on the chaining technique. There is, however, a key difference. Let Jmax be chosen such that 2 2 1/ VT. We then have due to the triangle inequality
Jwax
((P) = Suu
d(as, 1)
E Esup
+.tt 2 )9i
(2)
1=0
i=1
m
E sup
(uf
-
(3)
72
Junx
We bound Equation (2) and Equation (3) separately. For the latter, i.e., Equation (3), observe that
Σ
2
20

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
Applying the Cauchy-Schwarz inequallyyy Equation (3) and inserting this bound then yields
n Esup
n
n
E
9
MJ+1
72
n
Jmax
jmmax
2- 52222 2-2-2-Jam 2-max E O(1//n).
j=mmax
For the former, i.., Equation (2), observe that the variance bounds derived in the proof of the low dimensional case still valid. That is, we have that
(nnm²²)
for j 0, and DTW
1 o5+1 - u. 132 < max d(as, 16) E
On k2)
for j = O, and k-DTW otherwise.
t=1
O(n 2 2-)
Thus for some absolute constant c, for every j >
n
sup
-
)g:
S n log(2 11:loo; 2-1)))
7
m 22. 2/ 2-22 log² (mn=2)) 225
$
n
and for j = 0
1
c 2 log log?(mnz) )9:
E sup
n
Thus, we have
Jmax
c. m 24 log (mnz:2mmx 1 S (Jmax + +1)
E sup
Σ
(1
1. )
n
J 0=0
1=1
m. c.m-=4 x4 1lgoog (m))
0
n
since O(m). Combining both bounds then yields the claim.
Proof of Proposition 4.2. We first recall the corresponding bounds for median queries, that is, for curves of complexity 1. By tightness of Chernoff bounds (see for example Lemma of Klein & Young (2015)), these queries have Rademacher and Gaussian complexity of 2 (2(111)) 1/nn). Now for every such query, consider function space for which every point is duplicated m times, that is the point (or complexity 1 curve) a becomes complexity m curve dm- In this case d w (am, vm) = m ||o - .... Thus, every cost vector is sealed by exactly a factor m. By linearity of Rademacher and Gaussian complexity, this likewise increases these complexities by factor of m, yielding the claimed bound of 2 ////m//))
21

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
A.3. Robustness
We first observe that the sum of top-k elements of (non-negative) vector IR is indeed a norm. This is immediate from the Ky-Fan norm of diagonal matrices diag(U) E Rd whose diagonal entries are the coordinates of u. This holds since the Ky-Fan norm of order k is the sum of k largest singular values, which correspond to the & largest values in v. This correspondence has been exploited in recent loosely related work on sketching and k-sparsity in machine learning (Clarkson & Woodruff, 2015; Munteanu et al., 2021; 2022: 2023; Mai et al., 2023; Munteanu & Omlor, 2024) that inspired k-DTW.
We follow the outline of (Lopuhaä & Roussceuw, 1991, Section 2) and extend it towards a notion of the robustness for curves with respect to the k-DTW distance (along with its special cases, Fréchet and DTW). To the best of our knowledge, such a notion of robustness for curves has not been introduced or analyzed before.
(pi.... . Pm) in R. let tm (TT) equals the geometric median restricted to the top-k distances (Krivosija & Munteanu, 2019; Afshani & Schwiegelshohn, 2024) of the set {PI.... P. }. More formally, for all j E [ml] we define sj 3 E argmingeR! Enop. l|p: s//. We note that the argmin may be ambiguous. In that case we may choose an arbitrary but fixed element, i.e., we require that 51 = -.... = 8m. We finally note that Eepp. [|p: - a|| = de.prw(TT o)..
Given a curve
be its torve--ofot----meeeee
i.c., ($1,..., Sm) where each sq
It is easy to see that (T) is translational equivariant, which means that for any E I that we add simultaneously to all vertices of a curve, it holds that fm + v) tm (T) + v. We prove this property in Lemma A.9 below.
First, we define the breakdown point for fm with respect to k-DTW to be the smallest number S E I m of vertices to obtain Ty that equals π in all but many vertices that may be arbitrarily corrupted, such that og = tm (Te) is also arbitrarily corrupted. More formally, we define
8(tm, σ) = min{f E [m]] sup,, (tm (T), tm (Te)) = =c)
(4)
Obviously, it holds that (t (TT, tm (TT) = da.orw(o, σe) = || (ot) Since is is always finite for finite curves, the supremum is infinite if and only if the distance between the top-k-medians of corrupted and uncorrupted curves is infinite.
Lemma A.9. tm (T) is translational equivariant and as a consequence B(tm, x) is also translational equivariant.
Proof. Since Imm is determined by some choice of l vertices out of the vertices of π, we simply restrict one arbitrary but fixed choice of top-k indices 5 [ [m]] that determines the minimum. Then for any s E Rd and any translation E TRd we have that Eies Ipp - a|| Eiss (p(; + - (s + b. In particular this also holds for the minimizer. It thus follows that (T + v) = fm (T) + V.
For the second claim, note that Il (Tr u) that the supremum over all ne that differ from ı in vertices infinite if and only if the supremum over all m.. me + v that differ from n'
(m((m))) Im + = 1lt. (T)) -tm (fm((e)) + +w)ll = || (T) - Im (Te))l- This means
in l vertices is infinite.
Our aim is to prove that B(tm; TT) [ J. We start with the upper bound.
Lemma A.10. Let (Pi....,,Pm) be curve with pa E Rd. Let tm (x) a be the curve-offtop----edda Then 3(1, T) < 2
Proof. Since lm (TT) is translational equivariant by Lemma A.9, we can assume w.L.o.g. that 4m (T) = (0..... 0) of length
m. For the sake of contradiction. suppose that 3(tm, T) > | J. This implies that any tm (Tz), where ne is obtained from by corrupting& é = k+1 many vertices arbitrarily, must be bounded. That is, there exists L E R such that
(Te luop- S <0.
Consider vector IRd and let E+ be the set of vertices of iT that have largest (pe, v) and similarly let E_ be the set of l vertices of π that have largest (ps,-v), -v) in the opposite direction. These are the points that are furthest away from zero in both directions along the line spanned by v. Ties are broken according to the largest distance to the line spanned by u and arbitrarily if ties persist. Let E' = E, U E..
Now, consider the curve ()+r), that we obtain from π by adding v to the E vertices in E4. Similarly consider the curve T-)),, that we obtain from by subtracting e from the vertices in E_. The other vertices remain untouched.
22

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
If we let ||e|| grow large enough, then the top-k summands that determine either of mm (T(+))) Im (T(-)) dominated by the 28 2 l extreme elements in E and the other vertices p: E do not have an influence. We can thus simply remove the vertices p; $ E. Denote by *(+)), (-=)) the truncated sequences.
Since the number of corruptions are in each of the constructed curves, it follows from our assumption that [| (o)) llup = ml (lopp I and (T = ( (7)))) = || (#(-w)) v vlllop S
holds for some < co. Putting both bounds together, we get that
2L 2 (+(t)) - Vlllop. + Il (T(+)) Ilop. 2 || - (#(())))) Moog. + 11tm (T(+o)))lpps = kt -|
Thus, any large enough corruption vector that satisfies ||a|||
24 yields a contradiction.
remains prove the lower bound.
Lemma A.11. Let π (pI...., Pm)) be a curve with Pt E Rd. Let (m( = a be the curve-of-top--- Then ((tm, x) 2 k+1
Proof. Since fm (T) is translational equivariant by Lemma A.9, we can assume w.l.o.g. that tm (T) = (0..... ........) 0) of length m. Let M [|mm [|p:ll and let B(0 2M) be the ball of radius 2M centered at O. Let me == (.),...; 4m) a corrupted curve, obtained from by replacing at most & = 2
A=1 of its vertices by arbitrary vectors. Let tm (TT) be a curve
( 8), where minimizes Emp. k 11 $|), and let S C [m]] be a set of indices that determine the minimum.
We show that sup, [ltm top-k,,,, taken over all possible ô, is finite. We may assume that 8 & B(0, 2M) since otherwise Il (Te) Ilopp I 2MK is trivially finite. Let D = P(0.2M | bl be the smallest distance between å and (0, 2M). Then holds that
Im (TTe) [blpp = ||$|| < (D + 2M).
k
For any vertex qi in Ie that is corrupted, it holds by triangle inequality that
|1g: $|| 2 ||ail|
||
|/ (D + 2M).
(5)
Let us assume that large, that is, D> 2M - Since my E B(0, .). for each of the uncorrupted vertices 4 = P; of my (there are at least m of them), it holds that:
Ip..
a|| 2 M 2 D ||p/|--
(6)
The top-k values are attained by at most f= Thus, from Equations (5) and (6) holds that
k-1 2
corrupted vertices, and at least f= -h -1-11 uncorrupted ones.
Σ |gg: kp-
5|1 = Σ
11 $||
iES
Σ
lpp - $|| +
Σ
l1 - I|1
veS, uncormpted
iES, comupted
Σ
(1psal + D) +
Σ
(11 - (Dll-(D--000 + 2M))
KES, uncorrupted
iES, corrupted
k
) - (D + 2M)
k
1 + D.
k
2
iES
k:
))
k:
Σ
11 + D.
k k-2 2
2M
2
2
iES
k -
Σ
11 + D 2M
2
iES
11
iES
23

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
This contradicts the assumption that 4m (TT) minimizes Eiop.t |g: -81,, since 0 would be better top-k-median and the optimum can only be even smaller. Therefore it must hold that D I 2M-
R- Thus,
k
k
sup Il (Te) Itop-k S k (D+ (D+2M) S k- 2M
2M
2M -
< 0o
is finite. We conclude that B(tm, T) | + | J. as desired.
Overall, our above investigation proves the following theorem.
Theorem A.12 (Restatement of Theorem 2.4). Let (Pty...;Pum Pm)) be curve with pt E Rd. Let (T))
be the
curve-oftto-k-mmddie Then
k +
((mm; T)
2
B. Supplementary Experimental Material
All experiments were run HPC workstation with AMD Ryzen Threadripper PRO 5975WX, 32 cores at 3.6GHz, 512GB DDR4-3200. Our Python code is available at http::///itttta....oaaac/e//sses
B.1. Synthetic Data
The choice of the parameters for the curves A,, B and C, cf. Figure 1, that are used for our clustering experiment presented in Figures 2 and 5 is as follows:
the complexity of the curves m = 1 001;
the k-DTW distance parameter = [2.5 log(m)] = 17:
the number of "peaks" in the curves in A₁: I {5. 6,,7778)) 8};
the size of the "peaks" in the A-ttye eurves: I = 2- log(m)) 13.816;
the "small values" bound 0.2;
the number of curves of each type Ar. B. C: 20 (n 60).
B.2. Agglomerative Clustering
Clustering is important unsupervised Machine Learning problem, that aims at partitioning the input, consisting of data objects (often simply called points), such that "similar" points are grouped in the same part, while "dissimilar" points are assigned to different parts. Center based clustering such as k-means require to efficiently calculate center point for each of clusters. The input points are then assigned to the cluster represented by the closest center. Since computing a center based clustering for more than one curve is computationally hard even to approximate in most scenarios (Driemel et al., 2016; Buchin et al., 2019a; 2020; Bulteau al., 2020), as already mentioned in the introduction, we use a popular alternative called Hierarchical Agglomerative Clustering (HAC), which requires only the pairwise distances between the input data points. The partition process starts with each curve being singleton cluster. The current clusters then iteratively merged in ascending order of dissimilarity. Given dissimilarity measure d(a, b) for two curves, such Fréchet, DTW, kDDWW, the dissimilarity of two clusters A, B is defined via so called linkage functions. The arguably most popular linkage functions are single linkage d( A, B) = min.e A,bE d((a, b) and complete linkage d( A, B) = max A d(a, b), where the distance of two clusters is defined as the minimum resp. maximum distance of two input data points taken from each of the two clusters (Kaufman Rousseeuw, 1990).
novel
In Figure 5 (top) we see the results for single linkage clustering using the three distance measures. DTW (left) clearly has difficulties to distinguish between type-A and type-C curves, since the pairs (A,, C)) are very close, (A₁, B) moderately close, while (B, C)) are far from each other, violating the triangle inequality. The Fréchet distance (right) has very large intra-cluster distances between type-A, curves that are of the same magnitude as the inter-cluster distances. With slight adjustments to the curves' parameters, we can aggravate the situation such that Fréchet cannot cluster the curves correctly either. Note, that we did not create such an extreme example as would not only be synthetic but also handcrafted to bad situation. j-DTW (middle) can clearly identify the clusters, as the triangle inequality is less affected, while being robust to
24

---

Improved Learning via k-DTW: A Novel Dissimilarity Mcasure for Curves
the spikes of type-A, curves. As result, we obtain pure clusters whose intra-cluster distances are reasonably small and clearly distinguished from the large inter-cluster distances. The results for complete linkage very similar, cf. Figure (bottom).
DTW
k-DTW
FRÉCHET
SINGLE LINKAGE
TyzR
1.4
teas
140-
Trseh
1.-
Maad
Mans
90-
0.6
0.4
20
011111111
COMPLETE LINKAGE
Epe
3pe A Spe
1.8
Tpas
1807
1.4
1303
1.0
0.
002
403
0.4
202
in pm
Figure 5. Single (top) and complete (bottom) linkage clustering; DTW (left), k-DTW (middle), Fréchet distance (right); synthetic data.
B.3. 1-Nearest Neighbor Classification
Classification is important ML problem, where based input training set XM S X, consisting of M input points equipped with one of K labels, we classify the whole domain X into the K categories. The /-nearest neighbor (I-NN) model provides a well-known distance based classifier (Devroye et al., 2013). Let the input training set X consist of M pairs (X.. B6), where X₁ are from the instance domain X with a distance measure d X x X + 22.. and ys E [K], for all E [M]. Here, X is the set of polygonal curves in IRd, and the distance measures are the Fréchet, DTW, and k-DTW distances. Additionally, we perform experiments using several related distance measures: weak discrete Fréchet distance (Buchin et al., 2019c), edit distance with real penalty (Chen & Ng. 2004), and two variants of partial DTW distance (there are multiple distance measures under the same name in the literature). We use partial window DTW (Sakoe & Chiba, 1978), which matches vertices of each curve only within frame of bounded width w, and partial segment DTW (Tak & Hwang, 2007; Luo et al., 2024), which partitions both curves into L segments, each of which are matched via standard DTW. We set the window width to w 50 and the number of segments to L = 10 in all experiments with these partial DTW variants.
Then, curve T E X is classified into category E [K] if the (relative) majority of the I curves of X that have smallest distance to J are labeled with yı (Devroye al., 2013).
B.3.1. CLASSIFICATION OF THE OPEN UNIVERSITY LEARNING ANALYTICS DATASET
We first present the results obtained on the real-world data from the Open University Learning Analytics Dataset (OULAD) (Kuzilek et al., 2017). This dataset contains data about courses, students and their interactions with vir- tual learning environment. The clicks of student, aggregated by days, are represented as clickstreams, which we interpret as polygonal curves, in order to analyze them using the Fréchet, DTW, and our novel k-DTW distances.
We represent 275 clickstreams of one course (a course that started in "October 2014") as polygonal curves of complexity m 294. Each curve is labeled according to the achievement of the student in the course, as either "fail" (0) 46 students, or "pass" (1) 229 students. We use an I-NN model in order to predict the final exam result, which serves as a binary label indicating 'pass' or 'fail'. We note that the data set is very sparse, as it contains 56 027 vertices of the curves with value O. This amounts to 69.3% of all 80 850 vertices.
We run a 100 times repeated 6-fold cross validation, using I-NN with a standard choice of I = [vn] = 17 (cf. Devroye et al., 2013). We perform an exponential search for the best parameter E {2 E [8]} for the kDDTW distance, and a
25

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
subsequent finer search. The best results were obtained for k E (64, 76), which amounts to roughly 20% 25% of the curves' complexity. The results for all considered distance measures (the Fréchet distance, DTW, and k-DTW for various values of k) are given in Table 1. k-DTW outperformed the classification performance of Fréchet and DTW by margin of up to 8.2% resp. 1.8%, when measured by AUC. k-DTW also shows slight improvements in terms of accuracy and Fi-score
Table Binary classification of polygonal curves using l-nearest neighbor algorithm, on the real-world Open University Learning Analytics Dataset (OULAD) (Kuzilek et al., 2017). Mean classification performance measures (AUC, accuracy, Fi-score) taken over 100 independent repetitions 6-fold cross validation and standard errors "mean (std.err.)". Best and worst values are highlighted blue/red colors. At least one k-DTW variant always yields best or hetter while close to the best results compared either standard DTW or Fréchet.
Distance
AUC
Accuracy
Fj-Score
T(min)
T/TDTW
Fréchet
0.73737 (0.00194)
0,83742 (0.00072)
0.90953 (0. (0.00040)
1.7
1.0
2-DTW
0.74207 (0.00197)
0,83455 (0.00083)
0.90779 (0.00047)
77.4
47.9
4-DTW
0.75888 (0.00184)
0,83706 (0.00068)
0.90929 (0.00038)
80.8
50.0
8-DTW
0.77092 (0.00164)
0.83706 (0.00067)
0.90946 (0.00036)
78.5
48.6
16-DTW
0.76771 (0.00164)
0.83808 (0.00092)
0.90932 (0.00052)
73.7
45.6
32-DTW
0.78213 (0.00160)
0.84946 (0.00090)
0.91438 (0.00050)
68.9
42.6
56-DTW
0.79248 (0.00158)
0.85320 (0.00092)
0.91651 (0.00051)
62.8
38.8
60-DTW
0.79001 (0.00157)
0.85495 (0.00090)
0.91760 (0.00050)
61.7
38.2
64-DTW
0.78795 (0.00150)
0.85557 (0.00088)
0.91796 (0.00048)
60.6
37.4
68-DTW
0.78855 (0.00156)
0.85546 (0.00089)
0.91790 (0.00049)
59.5
36.8
72-DTW
0.79639 (0.00152)
0.85520 (0.00092)
0.91775 (0.00051)
58.3
36.0
76-DTW
0.79772 (0.00150)
0.85469 (0.00092)
0.91744 (0.00051)
57.6
35.6
80-DTW
0.79512 (0.00150)
0.85528 (0.00091)
0.91779 (0.00050)
56.3
34.8
84-DTW
0.79713 (0.00145)
0.85528 (0.00091)
0.91779 (0.00050)
55.2
34.1
88-DTW
0.79691 (0.00147)
0.85528 (0.00091)
0.91779 (0.00050)
54.2
33.5
92-DTW
0.79522 (0.00151)
0.85528 (0.00091)
0.91779 (0.00050)
53.2
32.9
96-DTW
0.79301 (0.00147)
0.85528 (0.00091)
0.91779 (0.00050)
52.3
32.3
100-DTW
0.79347 (0.00142)
0.85528 (0.00091)
0.91779 (0.00050)
51.3
31.7
104-DTW
0.79191 (0.00147)
0.85528 (0.00091)
0.91779 (0.00050)
50.5
31.2
108-DTW
0.78859 (0.00146)
0.85528
(0.00091)
0.91779 (0.00050)
49.7
30.7
112-DTW
0.78556 (0.00148)
0.85528
(0.00091)
0.91779 (0.00050)
49.0
30.3
116-DTW
0.78606 (0.00150)
0.85528
(0.00091)
0.91779 (0.00050)
48.1
29.7
120-DTW
0.78541 (0.00152)
0.85528 (0.00091)
0.91779 (0.00050)
47.5
29.4
124-DTW
0.78399 (0.00155)
0.85528 (0.00091)
0.91779 (0.00050)
46.8
28.9
128-DTW
0.78620 (0.00159)
0.85528
(0.00091)
0.91779 (0.00050)
46.4
28.7
256-DTW
0.77699 (0.00164)
0.85528
(0.00091)
0.91779 (0.00050)
34.1
21.0
DTW
0.78360 (0.00160)
0.85459 (0.00085)
0.91735 (0.00047)
1.6
1.0
EdiiRealPenalty
0.65800 (0.00261)
0.79892 (0.00335)
0.86557 (0.00348)
4.0
2.5
PartSegmDTW
0.54652 (0.00255)
0.79778 (0.00180)
0.88161 (0.00149)
0.2
0.1
PartWinDTWW
0.77959 (0.00175)
0.87823 (0.00051)
0.92956 (0.00031)
0.5
0.3
WeakFréchet
0.73917 (0.00204)
0.83618 (0.00073)
0.90896 (0.00041)
3.0
1.9
26

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
B.3.2. PARAMETER A: TUNING AND EVALUATION ON HOLD OUT DATA
In addition to our explicit parameter search, cross validated over the full data, we perform another hold out evaluation. Here the parameter & of the k-DTW distance is cross validated on training data, and the best value of le is then used on a hold out test data set, for I-nearest neighbor classification. For that sake, we split the input into training and test sets A and B, respectively. We randomly split the OULAD dataset (Kuzilek et al., 2017), where the test set B has (3: 4: 5 fraction of the input. We find the best value of k on A and evaluate it on B. Finally, we compare the performances of the Fréchet, k-DTW and DTW distances on the test set B. In all experiments we run 100 times repeated 6-fold cross- validation, using 1= [v[]]] for the (-NN training and test on the remaining hold out data.
The results are presented in Tables to In all of the experiments. the best k-DTW variant that is selected the training set is either best close the best, compared to the standard DTW and the Fréchet distance. Note that very small choices of the split size imply that the classification quality the test set significantly decreases (e.g. in Table 5).
Table 3. Binary classification of polygonal curves using (-nearest neighbor algorithm, on the real-world OULAD dataset (Kuzilek et al., 2017). Training set consists of / of the input set. Testing set remaining }. Mean classification performance measures (AUC, accuracy, Fi-score) taken over 100 independent repetitions of 6-fold cross validation and standard errors "mean (std.err.)" Best values are highlighted blue color.
Training
Distance
AUC
Accuracy
Fi-Score
Distance
AUC
Accuracy
F -i-ocore
2-DTW
0.71501
0.84599
0.91524
88-DTW
0.75375
0.85425
0.91969
4-DTW
0.70214
0.84653
0.91554
92-DTW
0.74882
0.85425
0.91969
8-DTW
0.70701
0.84845
0.91661
96-DTW
0.75097
0.85425
0.91969
16-DTW
0.69618
0.85288
0.91907
100-DTW
0.74912
0.85425
0.91969
32-DTW
0.71676
0.84858
0.91651
104-DTW
0.74578
0.85425
0.91969
56-DTW
0.74510
0.85508
0.92015
108-DTW
0.74237
0.85425
0,91969
60-DTW
0.75037
0,85524
0.92024
112-DTW
0.74483
0,85425
0,91969
64-DTW
0.75410
0,85192
0.91832
116-DTW
0.74176
0.85425
0,91969
68-DTW
0.76162
0.85431
0.91971
120-DTW
0.74261
0.85425
0.91969
72-DTW
0.76220
0.85437
0.91975
124-DTW
0.74078
0.85425
0.91969
76-DTW
0.75543
0.85426
0.91969
128-DTW
0.73960
0.85425
0.91969
80-DTW
0.75682
0.85404
0.91957
256-DTW
0.72549
0.85425
0.91969
84-DTW
0.75366
0.85425
0.91969
Testing
Distance
AUC
Accuracy
Fi Fi-Score
72-DTW
0.78912 (0.00382)
0.80103 (0.00266)
0.87266 (0.00174)
DTW
0.77772 (0.00381)
0.79724 (0.00258)
0,87005 (0.00167)
Fréchet
0.65995 (0.00542)
0.78542 (0.00144)
0.87542 (0.00087)
27

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
Table 4. Binary classification of polygonal curves using (-nearest neighbor algorithmm on the real-world OULAD dataset (Kuzilek et al., 2017). Training set consists / of the input set. Testing set remaining 3- Mean classification performance measures (AUC, accuracy. Fi-score) taken over 100 independent repetitions of 6-fold cross validation and standard emoors "mean (std.err.)". Best values are highlighted blue color.
Training
Distance
AUC
Accuracy
Fi-Score
Distance
AUC
Accuracy
Fi-Score
2-DTW
0.74698
0,83849
0.91098
88-DTW
0.77448
0.84538
0,91465
4-DTW
0.73626
0.83941
0.91141
92-DTW
0.77248
0.84538
0.91465
8-DTW
0.74288
0.83839
0,91089
96-DTW
0.77127
0.84538
0.91465
16-DTW
0.74744
0.83912
0.91130
100-DTW
0.77002
0.84538
0.91465
32-DTW
0.75834
0.83714
0.90998
104-DTW
0.76765
0.84538
0.91465
56-DTW
0.77456
0.84528
0.91459
108-DTW
0.76388
0.84538
0.91465
60-DTW
0.78048
0,84533
0.91462
112-DTW
0.76606
0.84538
0.91465
64-DTW
0.78281
0.84426
0.91401
116-DTW
0.76558
0.84538
0,91465
68-DTW
0.78641
0.84538
0.91465
120-DTW
0.76449
0.84538
0.91465
72-DTW
0.78423
0.84538
0,91465
124-DTW
0.76259
0.84538
0.91465
76-DTW
0.78071
0.84538
0.91465
128-DTW
0.76108
0.84538
0.91465
80-DTW
0.78088
0.84513
0.91451
256-DTWW
0.75135
0.84538
0.91465
84-DTW
0.77768
0.84538
0.91465
Testing
Distance
AUC
Accuracy
Fi Fi-Score
68-DTW
0.74092 (0.00533)
0.79057 (0.00164)
0.87842 (0.00102)
DTW
0.73140 (0.00583)
0.79001 (0.00159)
0,87812 (0.00098)
Fréchet
0,57310 (0.00665)
0.79696 (0.00022)
0.88270 (0.00028)
Table 5. Binary classification of polygonal curves using (-nearest neighbor algorithm, on the real-world OULAD dataset (Kuzilek et al.. 2017). Training set consists of of the input set. Testing set remaining 3. Mean classification performance measures (AUC, accuracy, Fi-score) taken over 100 independent repetitions of 6-fold cross validation and standard enrors "mean (std.err.)" Best values are highlighted blue color.
Training
Distance
AUC
Accuracy
Fi-Score
Distance
AUC
Accuracy
Fi-Score
2-DTW
0.77194
0.85320
0.91767
88-DTW
0.81430
0.85380
0.91729
4-DTW
0.77292
0.85021
0.91620
92-DTW
0,81094
0.85380
0.91729
8-DTW
0.76751
0.84344
0.91276
96-DTW
0,81126
0.85380
0.91729
16-DTW
0.77602
0.84038
0.91079
100-DTW
0.81037
0.85380
0.91729
32-DTW
0.79556
0.84879
0.91431
104-DTW
0.80934
0.85380
0.91729
56-DTW
0.81157
0.85394
0.91737
108-DTW
0.80691
0.85380
0.91729
60-DTW
0,81480
0,85394
0.91737
112-DTW
0.80950
0,85380
0.91729
64-DTW
0.81617
0.85348
0.91711
116-DTW
0.80972
0.85380
0.91729
68-DTWW
0.81908
0.85384
0.91732
120-DTW
0.80900
0.85380
0.91729
72-DTW
0.82163
0.85375
0.91726
124-DTW
0.80801
0.85380
0.91729
76-DTW
0.81766
0.85371
0.91724
128-DTW
0,80602
0.85380
0.91729
80-DTWW
0.81915
0.85357
0.91716
256-DTW
0.79856
0.85380
0.91729
84-DTW
0.81579
0.85380
0.91729
Testing
Distance
AUC
Accuracy
Fi Fi-Score
72-DTW
0.63990 (0.00602)
0.79996 (0.00021)
0.88358 (0.00031)
DTW
0.62175 (0.00675)
0.79996 (0.00021)
0.88358 (0.00031)
Fréchet
0.481 12 (0.00817)
0.79996 (0.00021)
0.88358 (0.00031)
28

---

Improved Learning via k-DTW; A Novel Dissimilarity Mcasure for Curves
B.3.3. CLASSIFICATION OF FURTHER DATASETS
We have evaluated the (-Nearest Neighbor Classification on additional datasets that have been used for evaluation of different distance measures in (Aghababa & Phillips, 2023). Their I-NN experiments are performed with / 5 and evaluated random 70/30 hold-out split, while choose / [v as for the previous OULAD (Kuzilek al., 2017) dataset and evaluate by a 6-fold cross validation, 100 times repeated independently. We compare k-DTW again against the discrete Fréchet and the DTW distance, as in the rest of our manuscript.
Here, we need to choose the value of k for our k-DTW distance. We will see that it is not needed to perform the extensive exponential or linear search, as in practice it suffices to choose some small value, compared to the input curves' complexity m. Thus, we compare the k-DTW for the values of & E (In(m), ym, m/10, m/4) 4), and we stress that the linear values only needed for short curves which was underlined by our theoretical results. Note that in the paper of Aghababa & Phillips (2023) there is no analysis of the complexity of the input curves m present these values, together with further descriptive parameters of the observed real-world datasets in Table 6.
Table 6. Description of the real- world datasets from (Aghababa & Phillips, 2023), where each curve has label from {0, 1J. the number the curves in dataset, m complexity of curves a dataset. d the dimension the ambient space.
Dataset
Reference
# Curves
Categories
Min
Max
Average
Dim.
m
m
m
d
Cars+Bus
(Cruz al., 2016)
120
(76, 44)
10
645
146
Sim. C+B
(Aghababa & Phillips, 2023)
446
(226, 220)
9
645
126
2
CharOuw
(Williams, 2008)
256
125),
89
153
117
2
Charlnw
(Williams, 2008)
255
(130, 125)
108
143
126
2
Char2nu
(Williams, 2008)
261
(130, 131)
92
182
120
Two Persons
(UIC, 2006)
213
(124, 89)
72
5 493
175
The dataset "Simulated C+B" (Aghababa & Phillips, 2023) was obtained from the dataset "Cars+Bus" (Cruz et al., 2016), to balance the number of input curves of the two classes by adding random noise to original input curves. For both the task is to distinguish between paths that are driven by car vs. bus. The "Characters" dataset (Williams, 2008) contains multiple Hand-writted characters, from which we picked three exemplary and challenging pairs (u,w), (n,w) and (n,u) be distinguished. Datasets are denoted here as "CharOuw", "CharInw" and "Char2nu", respectively. The "Two Persons" (UIC, 2006) dataset contains trajectories walked by two different persons to be distinguished. As it was done in (Aghababa & Phillips, 2023) for all datasets, we also removed stationary points along the trajectories, this does not change the shape of polygonal curve.
Tables 7 and 8 show the classification performance results: the means and standard errors over 100 independent repetitions. Additionally, we present the total running times for all experiments, and the ratio to the running time of the corresponding experiment using the DTW distance.
The best performing measure for each case is highlighted in blue, and the worst in red. One cases, kDDTW either still performs best, or close to the best. The only exception is "CharOuw" where ERP excels and beats all others by large margin. k-DTW is still second best in these cases. Notably, all competitors have some worst cases, while k-DTW is never worst.
that in the majority of
29

---

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
Table Mean classification performance measures (AUC, accuracy, Fi-score) taken over 100 independent repetitions 6-fold cross validation and standard errors "mean (std.err.)". Best and worst values highlighted in blue/red colors. Note that in half of the combinations of datasct/performance measure, some k-DTW variant is best, while worst results are mostly attained using standard DTW Fréchet. At least k-DTW variant always yields best better while close the best results compared to either standard DTW Fréchet. Datasets taken from (Aghababa & Phillips, 2023). Running time (7) given in minutes.
Data
Distance
AUC
Accuracy
Pi-Score
T(min)
TIT DTW
Fréchet
0.51511 (0.00390)
0.53158 (0.00355)
0.64938 (0.00299)
1.1
1.0
In(m)-DTW
0.54830 (0.00383)
0.56192 (0.00308)
0.67068 (0.00252)
5.3
5.0
vm-DTW
0.52259 (0.00369)
0.54058 (0.00280)
0.64863 (0.00261)
5.7
5.4
Cars+Bus
m/10-DTW
0.53635 (0.00342)
0,53008 (0.00323)
0.62415 (0.00301)
8.1
7.6
m/4-DTW
0.57633 (0.00329)
0,56250 (0.00266)
0.64711 (0.00264)
16.5
15.5
DTW
0.57590 (0.00321)
0.55417 (0.00273)
0.63637 (0.00269)
1.1
1.0
EdinRealPenalty
0.56580 (0.00324)
0,54900 (0.00258)
0.62282 (0.00269)
2.4
2.2
PartSegmDTW
0.54492 (0.00358)
0.58108 (0.00293)
0.70430 (0.00236)
0.2
0.1
PartWinDTW
0.58362 (0.00383)
0.60033 (0.00314)
0.71338 (0.00258)
0.8
0.7
WeakFréchet
0.51607 (0.00396)
0.53208 (0.00346)
0.64876 (0.00298)
1.7
1.6
Fréchet
0.88027 (0.00049)
0.77717 (0.00075)
0.76358 (0.00091)
25.0
1.1
In(m)-DTW
0.88748 (0.00046)
0.77291 (0.00074)
0.75119 (0.00092)
61.6
2.8
vmm-DWW
0.88966 (0.00045)
0.76037 (0.00073)
0.73046 (0.00098)
69.5
3.1
Sim. C+B
m/10-DDWW
0.89769 (0.00046)
0.76860 (0.00077)
0.72968 (0.00093)
97.4
4.4
m/4-DTW
0,91712 (0.00041)
0.79836 (0.00052)
0.76566 (0.00076)
158.5
7.1
DTW
0.91829 (0.00038)
0.79339 (0.00076)
0.75607 (0.00110)
22.3
1.0
EdinReal
0.90888 (0.00041)
0.79709 (0.00059)
0.76120 (0.00088)
50.6
2.3
PartSegmDTW
0,80593 (0.00088)
0,58766 (0.00071)
0,31972 (0.00168)
3.6
0.2
PTT
0.83221 (0.00068)
0.63397 (0.00092)
0.46484 (0.00178)
14.8
0.7
WeakFréchet
0.87942 (0.00047)
0.77073 (0.00071)
0.75483 (0.00089)
37.6
1.7
Fréchet
0.98094 (0.00029)
0.93426 (0.00053)
0.93568 (0.00056)
0.9
0.9
In(m)-DTW
0,98374 (0.00025)
0.93341 (0.00061)
0.93553 (0.00061)
12.5
11.9
Vm-DTW
0.98434 (0.00026)
0.93139 (0.00064)
0.93426 (0.00063)
14.9
14.1
CharOuw
m/10-DTW
0.98433 (0.00028)
0.92863 (0.00050)
0.93181 (0.00052)
15.8
15.0
m/4-DTW
0.98474 (0.00024)
0.92652 (0.00058)
0.93020 (0.00058)
21.1
20.1
DTW
0.98625 (0.00028)
0.91586 (0.00066)
0.92050 (0.00064)
1.1
1.0
EditRealPenalty
0.99819 (0.00009)
0.97906 (0.00025)
0.97930 (0.00029)
2.3
2.2
PartSegmDTW
0.99712 (0.00016)
0.97793 (0.00029)
0.97840 (0.00033)
0.1
0.1
PartWinDTW
0.98622 (0.00027)
0.91445 (0.00059)
0.91930 (0.00059)
0.7
0.6
WeakFréchet
0.97652 (0.00033)
0.92185 (0.00072)
0.92257 (0.00075)
1.2
1.1
30

---

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
Table Mean classification performance measures (AUC, accuracy, Fi-score) taken over 100 independent repetitions 6-fold cross validation and standard errors "mean (std.err.)". Best and worst values highlighted in blue/red colors. Note that in half of the combinations of datasct/performance measure, some k-DTW variant is best, while worst results are mostly attained using standard DTW Fréchet. At least k-DTW variant always yields best better while close the best results compared to either standard DTW Fréchet. Datasets taken from (Aghababa & Phillips, 2023). Running time (7) given in minutes.
Data
Distance
AUC
Accuracy
Pi-Score
T(min)
TIT DTW
Fréchet
0.91701 (0.00080)
0.83265 (0.00130)
0.82623 (0.00150)
3.3
1.1
In(m)-DTW
0.92853 (0.00063)
0.84517 (0.00114)
0.84209 (0.00120)
22.5
7.4
vm-DTW
0.94034 (0.00057)
0.86560 (0.00107)
0.86518 (0.001 13)
30.4
10.0
Charlnw lnw
m/10-DTW
0,94180 (0.00054)
0.86354 (0.00125)
0.86334 (0.00121)
39.0
12.9
m/4-DTW
0,95289 (0.00045)
0.88475 (0.00111)
0.88545 (0.00113)
45.1
14.9
DTW
0.95115 (0.00047)
0.87420 (0.00113)
0.87720 (0.00105)
3.0
1.0
EdinRealPenalty
0.95442 (0.00048)
0.86093 (0.00100)
0.85042 (0.00121)
6.9
2.3
PartSegmDTW
0.95931 (0.00042)
0.88577 (0.00089)
0.87933 (0.00099)
0.4
0.1
PartWinDTW
0.94604 (0.00051)
0.87546 (0.00109)
0.87802 (0.00107)
2.0
0.7
WeakFréchet
0.91767 (0.00083)
0.83866 (0.00139)
0.82806 (0.00164)
3.8
1.2
Fréchet
0.98326 (0.00026)
0.93725 (0.00074)
0.93259 (0.00084)
4.7
0.9
In(m)-DTW
0.98517 (0.00025)
0,94303 (0.00062)
0.93888 (0.00069)
23.2
4.3
vmm-DWW
0.98615 (0.00023)
0.94415 (0.00049)
0.94067 (0.00057)
30.0
5.5
Char2nu
m/10-DDWW
0.98816 (0.00018)
0.94228
(0.00053)
0.93861 (0.00063)
38.9
7.2
m/4-DTW
0.98949 (0.00016)
0.94757
(0.00048)
0.94475 (0.00057)
44.6
8.2
DTW
0.99376 (0.00019)
0.95534 (0.00045)
0.95348 (0.00048)
5.4
1.0
EdinRealPennaty
0.99830 (0.00007)
0.96695 (0.0 (0.00030)
0.96573 (0.00035)
12.3
2.3
PTr
0.99684 (0.0001I)
0,96116 (0.00038)
0,95963 (0.00043)
0.7
0.1
PTT
0.99355 (0.00019)
0.95519 (0.00045)
0.95334 (0.00049)
3.5
0.6
WeakFréchet
0.98281 (0.00025)
0.93364 (0.00066)
0.92836 (0.00075)
6.5
1.2
Fréchet
0.95373 (0.00058)
0.94832 (0.00002)
0.95324 (0.00021)
57.3
0.9
In(m)-DTW
0,95630 (0.00059)
0.94832 (0.00002)
0.95324 (0.00021)
655.2
10.4
Vm-DTW
0.95411 (0.00057)
0.94832 (0.00002)
0.95324 (0.00021)
962.6
15.3
Two Persons
m/10-DTW
0.96191 (0.00053)
0.94832 (0.00002)
0.95324 (0.00021)
1570.8
25.0
m/4-DTW
0.96426 (0.00055)
0.94390 (0. (0.00012)
0.94939 (0.00025)
2857.9
45.6
DTW
0,96115 (0.00053)
0,94832 (0.00002)
0.95324 (0.00021)
62.7
1.0
EditRealPenalty
0.85989 (0.00115)
0.77931 (0.00004)
0.76642 (0.00051)
130.5
2.1
ParlSegmDTW
0.95432 (0.00060)
0.90336 (0.00045)
0.90999 (0.00051)
6.1
0.1
PartWinDTW
0.94616 (0.00052)
0.91961 (0.00026)
0.92637 (0.00037)
35.0
0.6
WeakFréchet
0.95376 (0.00056)
0.94832 (0.00002)
0.95324 (0.00021)
92.7
1.5
31


Reviews:
[{"review_id": "HSVcw2zKe2", "reviewer": "Reviewer_MvAs", "summary": "This paper proposes a new distance measure called $k$-DTW, which is positioned as a interpolation between the classical DTW distance and the Fréchet distance. The technical novelty is to consider only the top $k$ matched distances in the alignment path, rather than summing all distances (as in DTW) or taking the maximum distance (as in Fréchet). The authors prove that $k$-DTW interpolates these two classical measures for $k = 1$ and $k$ sufficiently large. Empirical results show that $k$-DTW can yield stronger triangle-like properties than DTW, while still being more robust to outliers than Fr\\'echet. A parametric search algorithm is introduced for computing $k$-DTW exactly (as well as a $(1+\\varepsilon)$-approximation). The paper demonstrates applications in clustering (via hierarchical agglomerative clustering) and in nearest neighbor classification on synthetic and real-world datasets. The main contribution is that $k$-DTW addresses key shortcomings of Fréchet (outlier-sensitivity) and DTW (lack of metric-like properties) and, from experiments, appears beneficial in tasks like clustering and classification.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n**Question 1:** Formalize robustness.\n\n**Answer 1:** The concept of robustness for curve distance measures could be formalized as follows: given two curves whose matched vertices are at constant distance, say $1$, if we move one vertex away to increase the distance by a large value $\\Delta$, then the average distance contributed per vertex increases through this modification by $\\Delta/\\Theta(k)$ for $k$-DTW, $k\\in\\{1,\\ldots, m\\}$. This means that Fréchet is largely dominated by the single outlier, while for $k$-DTW the increase averages out, so that up to a factor $(1\\pm\\varepsilon)$, one single large perturbation of order $\\Delta \\approx \\varepsilon k$ is indistinguishable from tiny $\\varepsilon$ perturbations of (all) single vertices. This supports and quantifies the intuition and may be included as a lemma in our next revision.\n\nTo make the intuition more rigorous, we will examine the statistical breakdown point for $k$-DTW, which is defined to be the smallest fraction of vertices to be perturbed to corrupt the distance. A larger breakdown point indicates more robustness to arbitrary perturbations. As all $k$-DTW variants are closely related to the geometric median (minimizing a sum of distances), we will adapt the breakdown point analysis of the median [1] to our setting. It seems to be provable that the breakdown point of $k$-DTW is $\\lfloor \\frac{k+1}{2}\\rfloor/m$. This would imply that as long as $k\\in \\omega(1)$, the breakdown point is asymptotically larger than for Fréchet and thus considerably more robust. However, to reach a constant breakdown point that provides robustness comparable to DTW for arbitrarily long curves, $k$ would still need to be of order $\\Omega(m)$.\n\n[1] Lopuhaä, Rousseeuw - Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices, The Annals of Statistics, 1991\n\n\n\n**Question 2:** Heuristic strategies or data-structural optimizations to enhance the runtime.\n\n**Answer 2:** To enhance the runtime of our $k$-DTW algorithm *without* losing theoretical guarantees, we currently see two options:\n\n1) The current DTW subroutine is the plain DP algorithm without any tweaks. It could potentially be enhanced using heuristic DTW speed-ups such as [2] as a black box.\n\n2) Our first heuristic (line 206, right) could be enhanced by computing first only a subset of the DTW paths in a narrow band along the main diagonal. This works in linear $O(m)$ time and may be promising for reducing the variable 'mincost' early on so to cut off many unnecessary iterations.\n\nWe will also add the challenging open problem of improving the top-$k$ optimization framework that our algorithms build upon. This will hopefully yield provably faster exact algorithms for other top-$k$ problems as well.\n\n[2] Silva, Batista - Speeding up all-pairwise dynamic time warping matrix calculation, ICDM 2016.\n    \n\n\n**Question 3**: Additional baselines like partial DTW and weak Fréchet.\n\n**Answer 3**: Our claim is that $k$-DTW interpolates between the two extreme cases Fréchet and DTW. Comparisons to these two are thus most natural for supporting our claims. Please note that weak Fréchet has the same sensitivity to outlier vertices as standard Fréchet. Similarly, partial DTW admits only a factor $m$ triangle inequality. Hence, they do not contribute towards the goals of our paper.\n\nHowever, we agree on adding a few more baselines for completeness. We will thus include references, discussions and baseline experiments for partial DTW or weak Fréchet distance in addition to the suggestion of reviewer \"uWfM\". Please see our reply to \"uWfM\" for details and preliminary experiments.", "claims_and_evidence": "Claim 1: k-DTW is more robust to outliers than Fréchet distance.\nEvidence: The synthetic-clustering experiment shows how spikes in type-A curves heavily penalize Fréchet but do less harm under k-DTW. However, the paper does not provide a standalone \"robustness theorem.\" The authors rely primarily on intuitive arguments and empirical demonstrations.\n\nClaim 2: k-DTW has stronger metric-like properties than DTW.\nEvidence: They prove a relaxed triangle inequality with a factor of k, whereas DTW's violation can be worse by factors depending on curve length. The paper contains theoretical lemmas (especially Lemma 2.3) and the associated proofs. Empirically, the authors illustrate fewer pathological merges in clustering under k-DTW compared to DTW.\n\nClaim 3: The proposed k-DTW algorithm is feasible for practical use. \nEvidence: An exact algorithm and a (1+ε)-approximate algorithm are provided, though in worst cases it can be more expensive than classical DTW or Fréchet. The experiments show that it is slower than DTW and discrete Fréchet in practice.", "methods_and_evaluation_criteria": "The authors' methods include:\n\n- Defining k-DTW and demonstrating how to compute it via parametric search.\n- Evaluating clustering via HAC with single-linkage and complete-linkage.\n- Conducting l-nearest neighbor classification on real-world data.\n\nThese choices are appropriate to showcase the value of k-DTW in both supervised and unsupervised tasks. The design of synthetic data for highlighting robustness to peaks/outliers is quite clear. However, adding additional baseline distances like partial DTW or weak Fréchet could further solidify the empirical evaluations.", "theoretical_claims": "I checked the theoretical claims as laid out in Sections 2 and 3 of the paper:\n\n- The proof of the relaxed triangle inequality (Lemma 2.3) is good.\n- One point that is less formally addressed is the outlier-robustness: the paper does not contain a specialized \"robustness theorem.\" Instead, it uses examples and partial discussions to argue that k-DTW dilutes spikes in the alignment cost.", "experimental_designs_or_analyses": "- The authors constructed three curve types (A, B, C) to highlight the different shortcomings of Fréchet and DTW. This approach is sound: it clearly demonstrates how one or two spikes can dominate Fréchet, or how DTW can produce surprising alignments.\n- They then used hierarchical clustering (single-linkage and complete-linkage) and visually showed the intra-/inter-cluster distances. The analysis effectively highlights differences among the measures.\n- The real-world classification experiment (l-NN) is straightforward but adequate to underscore classification improvements. However, the paper could be enriched by including additional distance measures (partial DTW, weak Fréchet) for completeness.", "relation_to_broader_scientific_literature": "The paper explicitly compares $k$-DTW to the two classic distances: DTW and Fréchet. That is a direct relationship to established literature in computational geometry and time series analysis. We note that variants like weak Fréchet distance or partial DTW also exist, but they are not tested. The top-$k$ approach has precedents in top-$k$ optimization and the Ky-Fan norm (summing the $k$ largest singular values).I recommend referencing additional distances like partial DTW and weak Fr\\'echet which might be beneficial to help the robustness comparison.", "essential_references_not_discussed": "I recommend referencing additional distances like partial DTW and weak Fréchet.", "other_strengths_and_weaknesses": "Strengths:\n\n- Proposes a simple and new bridging distance between two classic curve distances.\n- Demonstrates some theoretical foundations like relaxed triangle inequality, dimension-free learning bounds, and provided practical benefits.\n- Proposed an algorithm to compute k-DTW, plus the (1+ε)-approximation.\n\nWeaknesses:\n\n- No explicit \"robustness theorem\" about outliers, only partial arguments via examples.\n- Time complexity is worse than classical DTW or discrete Fréchet distance, both in theory and experimental results.\n- The experimental comparisons could be further supported by including partial DTW, weak Fréchet, or other established distances for completeness.", "other_comments_or_suggestions": "na", "questions_for_authors": "You primarily demonstrate robustness to outliers through experiments. Could you formalize the observed outlier-robustness into a dedicated theorem or formal analysis?\n\nAre there specific heuristic strategies or data-structural optimizations you foresee to further enhance the runtime efficiency of the k-DTW algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yETcmgqGCb", "reviewer": "Reviewer_uWfM", "summary": "The paper proposes a new distance for between curves, the k-DTW distance, and make several types of compelling arguments for its use.  These include better near-metric properties than DTW, and better learning complexity than Frechet distance - k-DTW generalizes both.  The paper provides an efficient approximation algorithm (with clear provable guarantees), heuristics for improving runtime in practice while maintaining guarantees, and learning complexity results for learning a median curve from a set.  Each step involves non-trivial insights.  Moreover, the paper shows empirical improvement on synthetic (for clustering) and real data sets (for classification) that demonstrate clear improvement over the standard DTW and Frechet distances.  \n\nData analysis on curve data is an active area, and this paper provides an inventive and comprehensively presented new method in this area.  Moreover, I found it surprising that the new method works so well - it considers the longest k distances in a matched monotonic sequence (DTW uses all, and Frechet uses the 1 longest), and this has very different properties and seems to be more robust than either.  \n\nMoreover I found the paper clearly written.  It combines a variety of complicated theoretical and practical perspectives.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n**Question 1:** Edit Distance with Real Penalties, as in: Chen and Ng, VLDB 2004.\n        \n**Answer 1:**  We will include some references, discussions and baseline experiments for your suggestion along with another suggestion of reviewer \"MvAs\". Please see our reply to \"MvAs\" for details on the other distance measures.\n\nThe following table shows the results of our experiments, extended to weak Fréchet distance, partial DTW, and Edit Distance with Real Penalties, accompanied with the best performing $k$-DTW (cf. Table 4 in our submission). \n    \nThe best performing measure for each case is highlighted in $\\textcolor{blue}{\\text{blue}}$, and the worst in $\\textcolor{red}{\\text{red}}$. One can see that in the majority of cases, $k$-DTW either still performs $\\textcolor{blue}{\\text{best}}$, or $\\textcolor{orange}{\\text{close to the best}}$. The only exception is \"Char0uw\" where ERP excels and beats *all* others by a large margin. $k$-DTW is still second best in these cases. Notably, *all* competitors have some worst cases, while $k$-DTW is *never* worst.\n\n| Dataset    | Distance        | AUC (std.err.)| Accuracy (std.err.)       | $F_1$-Score (std.err.)    |\n|------------|-----------------|---------------------------------------|---------------------------------------|---------------------------------------|\n| Cars+Bus   | PartialDTW      | $\\textcolor{blue}{0.58362 (0.00383)}$     | $\\textcolor{blue}{0.60033 (0.00314)}$   | $\\textcolor{blue}{0.71338 (0.00258)}$  |\n|| WeakFréchet   | $\\textcolor{red}{0.51607 (0.00396)}$    | $\\textcolor{red}{0.53208 (0.00346)}$    | ${0.64876 (0.00298)}$       |\n|| EditRealPenalty | $0.56580 (0.00324)$         | $0.54900 (0.00258)$         | $\\textcolor{red}{0.62282 (0.00269)}$    |\n|| $m/4$-DTW       | $\\textcolor{orange}{0.57633 (0.00329)}$ | $\\textcolor{orange}{0.56250 (0.00266)}$ | $0.64711 (0.00264)$         |\n|\n| Sim.C+B    | PartialDTW      | $\\textcolor{red}{0.83221 (0.00068)}$    | $\\textcolor{red}{0.63397 (0.00092)}$    | $\\textcolor{red}{0.46484 (0.00178)}$    |\n|| WeakFréchet   | $0.87942 (0.00047)$         | $0.77073 (0.00071)$         | $0.75483 (0.00089)$         |\n|| EditRealPenalty | ${0.90888 (0.00041)}$       | ${0.79709 (0.00059)}$       | ${0.76120 (0.00088)}$       |\n|| $m/4$-DTW       | $\\textcolor{blue}{0.91712 (0.00041)}$   | $\\textcolor{blue}{0.79836 (0.00052)}$   | $\\textcolor{blue}{0.76566 (0.00076)}$   |\n|\n| Char0uw    | PartialDTW      | $0.98622 (0.00027)$         | $\\textcolor{red}{0.91445 (0.00059)}$    | $\\textcolor{red}{0.91930 (0.00059)}$    |\n|| WeakFréchet   | $\\textcolor{red}{0.97652 (0.00033)}$    | $0.92185 (0.00072)$         | $0.92257\t(0.00075)$         |\n|| EditRealPenalty | $\\textcolor{blue}{0.99819 (0.00009)}$   | $\\textcolor{blue}{0.97906 (0.00025)}$   | $\\textcolor{blue}{0.97930 (0.00029)}$   |\n|| $\\ln(m)$-DTW    | $\\textcolor{orange}{0.98374 (0.00025)}$ | $0.93341 (0.00061)$         | $0.93553 (0.00061)$        |\n|\n| Char1nw    | PartialDTW      | $0.94604 (0.00051)$         | ${0.87546 (0.00109)}$       | ${0.87802 (0.00107)}$       |\n|| WeakFréchet   | $\\textcolor{red}{0.91767 (0.00083)}$    | $\\textcolor{red}{0.83866 (0.00139)}$    | $\\textcolor{red}{0.82806 (0.00164)}$    |\n|| EditRealPenalty | $\\textcolor{blue}{0.95442 (0.00048)}$   | $0.86093 (0.00100)$         | $0.85042 (0.00121)$         |\n|| $m/4$-DTW       | $\\textcolor{orange}{0.95289 (0.00045)}$ | $\\textcolor{blue}{0.88475 (0.00111)}$   | $\\textcolor{blue}{0.88545 (0.00113)}$   |\n|\n| Char2nu    | PartialDTW      | ${0.99355 (0.00019)} $      | ${0.95519 (0.00045)}$       | ${0.95334 (0.00049)}$      |\n|| WeakFréchet   | $\\textcolor{red}{0.98281 (0.00025)}$    | $\\textcolor{red}{0.93364 (0.00066)}$    | $\\textcolor{red}{0.92836\t(0.00075)}$    |\n|| EditRealPenalty | $\\textcolor{blue}{0.99830 (0.00007)}$   | $\\textcolor{blue}{0.96695 (0.00030)}$   | $\\textcolor{blue}{0.96573 (0.00035)}$   |\n|| $m/4$-DTW       | $\\textcolor{orange}{0.98949 (0.00016)}$ | $\\textcolor{orange}{0.94757 (0.00048)}$ | $\\textcolor{orange}{0.94475 (0.00057)}$ |\n|\n| TwoPersons | PartialDTW | ${0.94616 (0.00052)}$ | ${0.91961 (0.00026)}$ | ${0.92637 (0.00037)}$ |\n|| WeakFréchet   | $0.95376 (0.00056)$         | $0.94832 (0.00002)$ | $0.95324 (0.00021)$         |\n|| EditRealPenalty | $\\textcolor{red}{0.85989 (0.00115)}$    | $\\textcolor{red}{0.77931 (0.00004)}$    | $\\textcolor{red}{0.76642 (0.00051)}$    |\n|| $m/10$-DTW      | $\\textcolor{blue}{0.96191 (0.00053)}$   | $\\textcolor{blue}{0.94832 (0.00002)}$   | $\\textcolor{blue}{0.95324 (0.00021)}$   |\n\n**Question 2:** More explicit parameter search over $k$.\n        \n**Answer 2:** We refer to Table 2 in the appendix of our submission for a more extensive parameter search over $k$, cross-validated and independently repeated $100$ times. We may add the suggested evaluation in the next revision.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes (for the most part), the properties proposed to justify the metric are clearly explained and stated formally.  The main proofs are proven or sketched in the main paper, and the ones deferred to the appendix make sense, and I did not find any concerns.", "experimental_designs_or_analyses": "They seem reasonable.  There are three experiments: clustering (synthetic -- it illustrates the advantages of k-DTW well), classification on learning analytics (theirs does best among DTW, Frechet), and classification letters/trajectories (theirs often does best).  \n\nI would have liked to have seen a more explicit parameter search over k on the training data, and then used once on evaluation data.", "relation_to_broader_scientific_literature": "I think it is fine.  It covers important aspects of curve distances, although it may be useful to compare to things like Edit Distance with Real Penalties:\n  Chen and Ng. \"On the marriage of lp-norms and edit distance\" in VLDB 2004", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9Zyq0ueHe2", "reviewer": "Reviewer_VKu5", "summary": "The paper proposes k-DTW (k-Dynamic Time Warping) as a dissimilarity measure between polygonal curves. The motivation is that many diverse datasets can be thought of as curves and measuring appropriately the distance between them is a fundamental problem.  Usually researchers has studied Frechet distances and DTW for this purpose and typically some transformations of one\ncurve into another is involved. However, both aforementioned measures have their disadvantages: Frechet distance is very sensitive to outlier whereas DTW is not a metric since it does not satisfy the triangle inequality.\n\nTo alleviate these issues with existing distances, the paper proposes k-DTW which combines advantages of standard measures like Frechet distance and of the standard DTW (essentially interpolating between the two), without their disadvantages. \n\nAt a high-level, the parameter k controls the degree of accuracy for the transformation performed between the two curves. Oftentimes, carrying out the whole trasformation may be expensive and also overfit to noise, whereas k-DTW only cares about the most important parts of the trasformation, as measured by a small subset of size k, and ignores the rest of the transformation. Although this may seem lossy it offers some advantages.\n\nThe main contributions of the paper are:\n\n1) The first point the authors make is that k-DTW satisfies a strengthened triangle inequality compared to DTW and it is thus closer to a proper metric, while retaining some robustness of DTW.\n\n 2) The second point is that there is an exact algorithm, as well as a (1 + eps)-approximation for k-DTW using a parametric search for the k-th largest matched distance with standard DTW on modified distance matrices as a subroutine. \n\n3) Next, they show the first dimension-free learning bounds for clustering under k-DTW and a separation result showing that k-DTW has strictly smaller Rademacher and Gaussian complexity than DTW for clustering curves. \n\n4) Finally, the authors provide experiments showing the benefits of k-DTW over the other two measures in the setting of clustering and nearest neighbor classification, on synthetic and real world data.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes, except the learning section 4.", "experimental_designs_or_analyses": "yes.", "relation_to_broader_scientific_literature": "Important relation since k-DTW could improve efficiency for comparing curves.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The conceptual message of the paper is that if we don't care about the whole computation of DTW or Frechet and we rather focus on the most important k parts of the computation then we can have good algorithms. The idea is that curves can be approximated by polygonal curves if we select some vertices on them and we connect them with affine segments, essentially interpolating between the points on the curves. \n\nThe main definition introduced in the paper is Definition 2.2 with a parameter k: as k increases we care about more and more pairs of large distances between the two curves; specifically, for k = 1 we recover the Frechet distance, and for k large\nenough we recover the DTW distance.\n\nI find the definition here very natural, and it comes as no surprise that once we focus on k terms in the summation, then then triangle inequality will be respected up to a multiplicative factor of k (Lemma 2.3).\n\nThe authors after introducing their k-DTW distance, they rule out some perhaps straighforward approaches. One thing that is notable is that the k-DTW distancε between two curves is NOT equal to just taking the largest k distances from the sum that yields their DTW distance. \n\nTheir first main result is to give an exact algorithm with runtime proportional to the description of the curves and the number of distinct pairwise distances. The analysis is non-trivial but it follows from the top-k framework of (Bertsimas & Sim, 2003).\n\nThe second main result is a (1+eps)-aox with a better runtime. The authors essentially shave off the number of distinct pairwise distances and replace it with the 1/eps x logarithm of k (say the accuracy eps is fixed small number). \n\nThe third main result, is what happens when we want to learn the median of curves sampled from a distribution over curves with vertices in the unit Euclidean ball of dimension d. The authors calculate the Rademacher and Gaussian complexities both for DTW and for k-DTW and they show how they can replace a strong dependence on the size of the polygonal curve with their parameter k.  Importantly, because k can be much smaller than dimension d, this provides a dimension-independent bound for learning.\n\nNo major weaknesses could be found.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces a new dissimilarity measure for polygonal curves called k-DTW, which improves on Dynamic Time Warping (DTW) by offering stronger metric properties and greater robustness to outliers. It provides both exact and approximate algorithms, theoretical learning bounds, and shows improved performance in clustering and nearest neighbor tasks. k-DTW also needs fewer samples than DTW.

All reviewers are positive about the paper. No major issues were raised, while minor ones were largely addressed in the rebuttal. 

The finals scores are 3xAccept.

In addition to the theoretical contribution, the reviewers, overall, also appriciated the experiments (related to clustering and classification) and how they provided empirical evidence to support the authors' claims. 

In the AC's view, this is a clear Accept.
Decision: Accept (poster)