Pith. sign in

REVIEW 2 major objections 3 minor 61 references

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

T0 review · 2 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read k-DTW, which charges a traversal only its k largest matched distances, provably combines Fréchet's metric-like structure with DTW's outlier robustness and reduces the sample complexity of learning median curves by a factor ~sqrt(m) when k…

desk verdict Genuinely new measure with sound algorithmic and learning-theoretic results; the cited Lemma 2.3 counterexample dissolves on inspection. read the letter →

arxiv 2505.23431 v1 pith:BUIQW6S4 submitted 2025-05-29 cs.DS cs.CGcs.LGstat.ML

Amer Krivošija , Alexander Munteanu , André Nusser , Chris Schwiegelshohn This is my paper
classification cs.DScs.CGcs.LGstat.ML
keywords k-DTWdynamictimewarpingFréchetdistancepolygonalcurvesRademachercomplexityGaussiansamplebreakdownpoint
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces k-DTW, a dissimilarity measure for polygonal curves defined as the minimum, over all monotone matchings between the curves, of the sum of the $k$ largest matched vertex distances. The paper's central aim is to show that k-DTW combines the metric-like behavior of the Fréchet distance with the outlier robustness of dynamic time warping (DTW), and that it makes curve learning provably more sample-efficient than DTW. They prove a relaxed triangle inequality with factor $k$, a breakdown point of roughly $k/2$, an exact $O(m'm''z)$ algorithm, and the first dimension-free Rademacher and Gaussian complexity bounds for learning median curves. The headline result is a separation: when $k$ is much smaller than the curve complexity $m$, k-DTW's complexity bound is smaller than DTW's by a factor of order $\sqrt{m}$. If true, this means practitioners can learn median curves from far fewer trajectories by choosing a small $k$, without sacrificing robustness to outliers.

What carries the argument

The central algorithmic object is a parametric search over the $k$-th largest matched distance. Algorithm 1 sorts the $z$ distinct pairwise distances between vertices of the two curves, and for each candidate threshold $E[l]$ it computes DTW on the truncated matrix $\max\{D[i,j]-E[l],0\}$, then adds $kE[l]$; the proof shows the optimal k-DTW traversal is recovered at the iteration where the threshold is the smallest of its $k$ largest distances, and no other iteration underestimates this cost. On the learning side, the machinery is chaining over $\varepsilon$-nets of cost vectors induced by median curves, with terminal embeddings—low-distortion maps that preserve distances from a point set to arbitrary query points—that remove the ambient dimension while preserving DTW and k-DTW distances, giving net sizes that scale with $k$ instead of $m$.

What would settle it

Compute the covering number of cost vectors induced by ordered $m$-tuples of median curves under $k$-DTW after a terminal embedding to dimension $O(k^2\varepsilon^{-2}\log(mn))$; if the net size is $\exp(\Omega(mk^2\log^2(mn)\varepsilon^{-2}))$ rather than $\exp(O(mk^2\log^2(mn)\varepsilon^{-2}))$, the separation drops. Alternatively, on a high-dimensional curve distribution with $k=O(\log m)$, measure the excess-risk decay of the empirical median under $k$-DTW versus DTW; a gap below $\tilde{\Omega}(\sqrt{m})$ contradicts the claim.

Watch

Extended reading notes

Core claim

k-DTW generalizes the discrete Fréchet distance ($k=1$) and the standard DTW distance ($k \ge 2m-1$) by charging a traversal only its $k$ largest matched Euclidean distances and ignoring the rest. The paper claims this measure has the best of both worlds: it obeys a relaxed triangle inequality $d_{k\text{-DTW}}(\sigma,\tau) \le k\,(d_{k\text{-DTW}}(\sigma,\upsilon)+d_{k\text{-DTW}}(\upsilon,\tau))$ that is tight and avoids the $m$-factor violation of DTW, and it has a finite-sample breakdown point of $\lfloor (k+1)/2\rfloor$ for the curve-of-top-$k$-median, interpolating between Fréchet's fragility and DTW's robustness. Algorithmically, the k-DTW distance can be computed exactly by a parametric search over the $k$-th largest matched distance, running standard DTW on the matrix $D'[i,j]=\max\{D[i,j]-E[l],0\}$ and adding $kE[l]$ for each threshold guess $E[l]$. The learning-theoretic part bounds the Rademacher and Gaussian complexities of learning the median curve by $O\bigl(\sqrt{mk^2\min\{d\log k,\,k^2\log^4(mn)\}/n}\bigr)$, versus $O\bigl(\sqrt{m^3\min\{d\log m,\,m^2\log^4(mn)\}/n}\bigr)$ for DTW, with a matching DTW lower bound of $\Omega(\sqrt{m^2/n})$; this yields a separation by $\tilde{\Omega}(\sqrt{m})$ when $k\ll m$. The paper also reports experiments where k-DTW outperforms both Fréchet and DTW in agglomerative clustering and $l$-nearest-neighbor classification.

Load-bearing premise

The whole improvement rests on the assumption that after projecting the sample into a low-dimensional space, a small covering of median curves exists whose size depends on $k$ and not on the vertex order; if the covering must track the order of the $m$ vertices, the claimed $\tilde{\Omega}(\sqrt{m})$ advantage over DTW shrinks.

Editorial extensions

If this is right

  • For learning the median of $m$-vertex curves, using k-DTW with $k\ll m$ replaces factors of $m$ in the sample-complexity bound by factors of $k$, shrinking the bound from roughly $m^3$ to roughly $mk^2$.
  • The Rademacher and Gaussian complexities under k-DTW are smaller than under DTW by a factor $\tilde{\Omega}(\sqrt{m})$ when $k\ll m$, so fewer observed curves are needed to learn a median with the same confidence.
  • Computing k-DTW exactly takes $O(m'm''z)$ time, where $z$ is the number of distinct pairwise distances, and a $(1+\varepsilon)$-approximation runs in $O(m'm''\log(k/\varepsilon)/\varepsilon)$ time.
  • k-DTW satisfies a relaxed triangle inequality with factor $k$ and has a finite-sample breakdown point of $\lfloor(k+1)/2\rfloor$, placing it between Fréchet's metricity and DTW's outlier tolerance.
  • In the reported experiments on synthetic curves and real-world clickstream and trajectory data, k-DTW improves over Fréchet and DTW in agglomerative clustering and $l$-nearest-neighbor classification.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the paper is right, the parameter $k$ is an interpretable robustness-and-efficiency knob: sample complexity scales roughly with $k^2$, while robustness to outliers degrades only linearly in $k$, so moderate values around $\log m$ may hit the practical sweet spot.
  • The parametric-search trick used for k-DTW could transfer to other top-$k$ dissimilarities or robust variants of sequence distances where a standard dynamic program exists but the top-$k$ objective is not directly decomposable along paths.
  • The dimension-free bounds suggest that in high-dimensional trajectory data the bottleneck for learning medians is curve complexity $m$, not ambient dimension $d$; a testable consequence is that embedding-based curve-clustering pipelines should see gains concentrated in the $m$-dependent rather than $d$-dependent regime.
  • The $\tilde{\Omega}(\sqrt{m})$ separation is a worst-case bound; whether real datasets exhibit that full gap is an empirical question the paper's classification experiments only partially address.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper introduces k-DTW, a dissimilarity measure for polygonal curves that interpolates between the discrete Fréchet distance (k=1) and DTW (k large enough). It proves a relaxed triangle inequality with optimal factor k, establishes a breakdown point of floor((k+1)/2) for the curve-of-top-k-median estimator, gives an exact O(m'm''z) algorithm and a (1+ε)-approximation algorithm for computing k-DTW, and derives Rademacher and Gaussian complexity bounds for learning the median curve. The main theoretical claim is a dimension-free upper bound of O(sqrt(m k^2 min{d log k, k^2 log^4(mn)}/n)) under k-DTW versus O(sqrt(m^3 min{d log m, m^2 log^4(mn)}/n)) under DTW, together with a DTW lower bound of Omega(sqrt(m^2/n)), yielding an Omega~(sqrt(m)) separation for small k. Experiments on synthetic and real-world data illustrate the practical benefits of k-DTW for clustering and classification.

Significance. If the results are correct, this is a significant contribution to the learning theory of curves: it provides the first dimension-free complexity bounds for median learning under curve distances and exposes a concrete separation between k-DTW and DTW. The algorithmic part is also valuable, giving an exact algorithm and a near-quadratic (1+ε)-approximation for a new distance measure. The paper is largely self-contained, includes machine-checkable code, and the theoretical claims are accompanied by reproducible experiments. However, two technical points in the proof of the main learning bound need correction: the covering argument in Lemma 4.3 overlooks curves with repeated vertices, and the stated bounds collapse at k=1 (the Fréchet case). Both issues are local and do not appear to change the asymptotic separation, but they must be addressed before the paper is fully rigorous.

major comments (2)
  1. [Lemma 4.3 (and Lemma A.8)] The net is constructed from all subsets S ⊆ C of size |S| = m. A curve ψ with repeated vertices can map to a multiset of covering centers of size less than m, so it is not represented by any subset of size m. The proof should use ordered m-tuples from C (with repetition allowed); this replaces binom(|C|,m) by |C|^m = exp(c·h·m·log(1/ε')). After substituting ε' = ε/(2m) for DTW and ε' = ε/(2k) for k-DTW, the resulting net-size bounds are the same asymptotically as those claimed in Lemma 4.3, so the main theorem survives, but the proof as written is not valid.
  2. [Theorem 4.1 / Lemma 4.3] For k=1, the stated bound O(sqrt(m k^2 · min{d log k, k^2 log^4(mn)}/n)) contains log k = 0, making the right-hand side zero for the Fréchet-distance case. This is impossible because the Fréchet distance (k=1) has positive Rademacher complexity. The issue originates in the net-size expression exp(c·d·m·log(k/ε)): the correct expression is exp(c·d·m·log((k+1)/ε)) (or equivalently log(2k/ε)), since the sensitivity of k-DTW to vertex perturbation is 2kε' and for k=1, ε=1, a constant-size net is required. Please correct the statement and proof; the asymptotic separation for k ≥ 2 is unaffected.
minor comments (3)
  1. [Proposition 4.2] The proposition says 'Let D be an arbitrary distribution' but the proof constructs a specific distribution via the reduction from point queries. The statement should be rephrased as 'there exists a distribution D' (or 'for any distribution D, the worst-case complexity over samples is Omega(...)'), since the proof as written only establishes existence.
  2. [Abstract and Section 4] The separation 'by a factor Omega~(sqrt(m)) when k << m' is stated informally. The formal bounds imply that the ratio is sqrt(m)/k^2 (up to log factors), so the stated separation requires k = O(polylog(m)) or more generally k = m^{o(1)} with k^2 = O(polylog(m)). Please qualify the claim accordingly.
  3. [Section 4 / Appendix A.2] The high-dimensional chaining proof is compressed. Please state explicitly that a single terminal embedding is applied to the sample vertices, that all nets are constructed in the embedded space, and that the Gaussian complexity of the original class is bounded (up to constants) by the embedded class via the preservation guarantee. This would resolve the ambiguity about whether different chaining levels use different embeddings.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the k-DTW learning bounds are derived from the definition via chaining, terminal embeddings, and covering nets, with no fitted parameter or load-bearing self-citation.

full rationale

The paper's central claims are self-contained derivations from the definition of k-DTW. Algorithm 1 is proven correct by a case analysis over the sorted distinct distances (Theorem A.1), and the approximation follows by rounding and the Frechet k-approximation (Lemma A.2, A.3). The learning-theoretic bounds (Theorem 4.1) are obtained by chaining over epsilon-nets of cost vectors; the low-dimensional net size is proved directly by covering the unit ball (Lemma 4.3), and the dimension-free version combines this with the external terminal embedding theorem of Narayanan and Nelson (2019) (Lemma A.7, A.8). No parameter is fitted to data in these derivations: the k in the bounds is the same free parameter appearing in the definition of k-DTW, and the DTW lower bound (Proposition 4.2) is a reduction from point-median complexity, not an assumption of the sought result. The alleged tightness example for Lemma 2.3 is valid, as a monotone traversal matches the two zero-vertex blocks of upsilon and tau with cost zero; the net-counting concern about ordered tuples changes only the constant in the exponent, not the stated bounds. Self-citations (e.g., Krivosija and Munteanu 2019, Afshani and Schwiegelshohn 2024 for top-k geometric median) appear only as background and are not load-bearing for the main theorem. The empirical section tunes k and uses hold-out evaluation, but no empirical fit is used to derive or justify the theoretical bounds. I therefore find no circular step.

Assumptions & free parameters 1 free parameters · 6 assumptions · 1 invented entities

Most of the paper's central claims are derived from first principles or standard tools. The only parameter chosen by hand in the experimental section is k, which is cross-validated; it does not enter the proofs. The proofs assume standard results: triangle inequality, covering numbers, terminal embeddings, and exact DTW dynamic programming. The new entity is the k-DTW distance itself, which is fully defined and testable.

free parameters (1)
  • k in experimental evaluation = 64, 72, 76 on OULAD; ln(m), sqrt(m), m/10, m/4 on other datasets
    k is an input to the measure, but in experiments it is selected by cross-validation. This is parameter fitting for the empirical comparison, though the theoretical claims treat k as given.
assumptions (6)
  • standard math Euclidean triangle inequality and standard covering number bounds for balls in R^d
    Used throughout, e.g., Lemma 2.3 and Lemma 4.3.
  • standard math Existence of terminal embeddings with target dimension O(epsilon^{-2} log|P|) (Narayanan and Nelson, 2019)
    Invoked in Lemma A.7 and Lemma A.8 to remove dependence on ambient dimension d.
  • standard math Standard DTW dynamic program computes DTW exactly in O(m'm'')
    Used as subroutine in Algorithm 1 and the approximation; cited to Berndt and Clifford, and Vintsyuk.
  • standard math Rademacher and Gaussian complexity control excess risk for Lipschitz losses (Bartlett and Mendelson, 2002)
    Bridges Theorem 4.1 to the sample-complexity claim.
  • domain assumption Curves are supported in the unit Euclidean ball and have complexity exactly m; median curves are restricted to the same class
    Stated in Section 4; all learning bounds are relative to this normalization.
  • domain assumption Discrete traversals are monotone with the stated start/end constraints; k-DTW fills missing entries with zeros when k exceeds traversal length
    Definition 2.2; a technical convention used in algorithms and proofs.
invented entities (1)
  • k-DTW distance independent evidence
    purpose: New dissimilarity measure for polygonal curves; sum of the k largest matched vertex distances under a traversal
    Fully defined in Definition 2.2, computable, and empirically evaluated; learning and robustness theorems provide falsifiable properties.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves." pith.science (2026). https://pith.science/paper/BUIQW6S4

@misc{pith2026250523431,
  author       = {Pith},
  title        = {Pith review of: Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BUIQW6S4}},
  note         = {Machine review of arXiv:2505.23431}
}
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\'{e}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.

Figures

Figures reproduced from arXiv: 2505.23431 by the authors.

Figure 1
Figure 1. Curves of type A2 (left); type B (middle); type C (right) DTW k-DTW Frechet ´ Single linkage 0 20 40 60 80 100 120 140 160 Type A Type B Type C Mixed 0 1 2 3 4 5 6 7 8 Type A Type B Type C Mixed 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 Type A Type B Type C Mixed Complete linkage 0 200 400 600 800 1000 1200 1400 Type A Type B Type C Mixed 0 5 10 15 20 25 Type A Type B Type C Mixed 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 Type A Ty… view at source ↗
Figure 2
Figure 2. Single (top) and complete (bottom) linkage clustering; DTW (left), [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. K-gadget (left); D-gadget (right); traversals realizing k-DTW (blue); traversals realizing DTW (red). 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.… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Example curves used to prove Lemma A.5. An example instance that has a long DTW [PITH_FULL_IMAGE:figures/full_fig_p027_4.png]
Figure 5
Figure 5. Figure 5: Single (top) and complete (bottom) linkage clustering; DTW (left), [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

61 extracted references · 56 canonical work pages

  1. [1]

    Abboud, A., Ba c kurs, A., and Williams, V. V. (2015). Tight hardness results for LCS and other sequence similarity measures. In Proc. of the 56th IEEE Symposium on Foundations of Computer Science, (FOCS) , pages 59--78

    work page 2015

  2. [2]

    and Schwiegelshohn, C

    Afshani, P. and Schwiegelshohn, C. (2024). Optimal coresets for low-dimensional geometric median. In International Conference on Machine Learning, (ICML) , pages 262--270

    work page 2024

  3. [3]

    K., Ben Avraham , R., Kaplan, H., and Sharir, M

    Agarwal, P. K., Ben Avraham , R., Kaplan, H., and Sharir, M. (2014). Computing the discrete F r \' e chet distance in subquadratic time. SIAM Journal on Computing , 43(2):429--449

    work page 2014

  4. [4]

    Aghababa, H. P. and Phillips, J. M. (2023). An experimental study on classifying spatial trajectories. Knowl. Inf. Syst. , 65(4):1587--1609

    work page 2023

  5. [5]

    and Godau, M

    Alt, H. and Godau, M. (1995). Computing the Fr\'echet distance between two polygonal curves. International Journal of Computational Geometry & Applications , 5:75--91

    work page 1995

  6. [6]

    Bartlett, P. L. and Mendelson, S. (2002). Rademacher and G aussian complexities: Risk bounds and structural results. Journal of Machine Learning Research , 3:463--482

    2002

  7. [7]

    Berndt, D. J. and Clifford, J. (1994). Using dynamic time warping to find patterns in time series. In Proc. of the 3rd International Conference on Knowledge Discovery and Data Mining, ( AAAIWS ) , pages 359--370

    work page 1994

  8. [8]

    and Sim, M

    Bertsimas, D. and Sim, M. (2003). Robust discrete optimization and network flows. Math. Program. , 98(1-3):49--71

    work page 2003

Show all 61 references
  1. [9]

    Brankovic, M., Buchin, K., Klaren, K., Nusser, A., Popov, A., and Wong, S. (2020). (k, l)-medians clustering of trajectories using continuous dynamic time warping. In Proc. of the 28th ACM International Conference on Advances in Geographic Information Systems, ( SIGSPATIAL ) ,...

    2020

  2. [10]

    Bringmann, K. (2014). Why walking the dog takes time: F r\'echet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. of the 55th IEEE Symposium on Foundations of Computer Science, (FOCS) , pages 661--670

    2014

  3. [11]

    and K \" u nnemann, M

    Bringmann, K. and K \" u nnemann, M. (2015). Quadratic conditional lower bounds for string problems and dynamic time warping. In Proc. of the 56th IEEE Symposium on Foundations of Computer Science, (FOCS) , pages 79--97

    2015

  4. [12]

    and Mulzer, W

    Bringmann, K. and Mulzer, W. (2016). Approximability of the discrete F r \' e chet distance. Journal of Computational Geometry , 7(2):46--76

    2016

  5. [13]

    and Driemel, A

    Br \" u ning, F. and Driemel, A. (2023). Simplified and improved bounds on the VC -dimension for elastic distance measures. CoRR , abs/2308.05998

    2023 arXiv

  6. [14]

    S., Larsen, M

    Bucarelli, M. S., Larsen, M. F., Schwiegelshohn, C., and Toftrup, M. (2023). On generalization bounds for projective clustering. In Advances in Neural Information Processing Systems, (NeurIPS) , pages 71723--71754

    2023

  7. [15]

    Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., L \" o ffler, M., and Struijs, M. (2019a). Approximating (k, ) -center clustering for curves. In Proc. of the 30th ACM-SIAM Symposium on Discrete Algorithms, (SODA) , pages 2922--2938

    2019

  8. [16]

    Buchin, K., Driemel, A., and Struijs, M. (2020). On the hardness of computing an average curve. In Proc. of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, (SWAT) , pages 19:1--19:19

    2020

  9. [17]

    Buchin, K., Driemel, A., van de L'Isle, N., and Nusser, A. (2019b). klcluster: Center-based clustering of trajectories. In Proc. of the 27th ACM International Conference on Advances in Geographic Information Systems, ( SIGSPATIAL ) , pages 496--499

    2019

  10. [18]

    Buchin, K., Nusser, A., and Wong, S. (2022). Computing continuous dynamic time warping of time series in polynomial time. In Proc. of the 38th International Symposium on Computational Geometry, (SoCG) , pages 22:1--22:16

    2022

  11. [19]

    Buchin, K., Ophelders, T., and Speckmann, B. (2019c). SETH says: Weak F r \' e chet distance is faster, but only if it is continuous and in one dimension. In Proc. of the 30th ACM-SIAM Symposium on Discrete Algorithms, (SODA) , pages 2887--2901

    2019

  12. [20]

    Buchin, M. E. (2007). On the Computability of the Frechet Distance Between Triangulated Surfaces . Dissertation, FU Berlin

    2007

  13. [21]

    Bulteau, L., Froese, V., and Niedermeier, R. (2020). Tight hardness results for consensus problems on circular strings and time series. SIAM J. Discret. Math. , 34(3):1854--1883

    2020

  14. [22]

    and Ng, R

    Chen, L. and Ng, R. T. (2004). On the marriage of lp-norms and edit distance. In Proc. of the 30th International Conference on Very Large Data Bases, (VLDB) , pages 792--803

    2004

  15. [23]

    and Huang, H

    Cheng, S. and Huang, H. (2024). Solving F r \' e chet distance problems by algebraic geometric methods. In Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms, (SODA) , pages 4502--4513

    2024

  16. [24]

    Clarkson, K. L. and Woodruff, D. P. (2015). Sketching for M-estimators: A unified approach to robust regression. In Proc. of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA) , pages 921--939

    2015

  17. [25]

    Cohen - Addad, V., Draganov, A., Russo, M., Saulpic, D., and Schwiegelshohn, C. (2025). A tight VC -dimension analysis of clustering coresets with applications. In Proc. of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA) , pages 4783--4808

    2025

  18. [26]

    Conradi, J., Kolbe, B., Psarros, I., and Rohde, D. (2024). Fast approximations and coresets for (k, l)-median under dynamic time warping. In 40th International Symposium on Computational Geometry, (SoCG) , pages 42:1--42:17

    2024

  19. [27]

    Cruz, M., Macedo, H., Barreto, R., and Guimares, A. (2016). GPS Trajectories . UCI Machine Learning Repository. https://doi.org/10.24432/C54S5Z

    2016 doi

  20. [28]

    Devroye, L., Gy \"o rfi, L., and Lugosi, G. (2013). A probabilistic theory of pattern recognition , volume 31 of Applications of Mathematics -- Stochastic Modelling and Applied Probability . Springer

    2013

  21. [29]

    and Krivo s ija, A

    Driemel, A. and Krivo s ija, A. (2018). Probabilistic embeddings of the F r \' e chet distance. In Proc. of the 16th International Workshop on Approximation and Online Algorithms, (WAOA) , pages 218--237

    2018

  22. [30]

    Driemel, A., Krivo s ija, A., and Sohler, C. (2016). Clustering time series under the Fr \' e chet distance. In Proc. of the 27th ACM-SIAM Symposium on Discrete Algorithms, (SODA) , pages 766--785

    2016

  23. [31]

    M., and Psarros, I

    Driemel, A., Nusser, A., Phillips, J. M., and Psarros, I. (2021). The VC dimension of metric balls under F r \' e chet and H ausdorff distances. Discrete & Computational Geometry , 66(4):1351--1381

    2021

  24. [32]

    and Mannila, H

    Eiter, T. and Mannila, H. (1994). Computing discrete F r \'e chet distance. Technical Report CD-TR 94/64, Christian Doppler Laboratory

    1994

  25. [33]

    Fan, K. (1951). Maximum properties and inequalities for the eigenvalues of completely continuous operators. Proc. of the National Academy of Sciences , 37(11):760--766

    1951

  26. [34]

    Foster, D. J. and Rakhlin, A. (2019). _ vector contraction for R ademacher complexity. CoRR , abs/1911.06468

    2019 arXiv

  27. [35]

    Garfinkel, R., Fern \'a ndez, E., and Lowe, T. J. (2006). The k -centrum shortest path problem. Top , 14:279--292

    2006

  28. [36]

    and Sharir, M

    Gold, O. and Sharir, M. (2018). Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. ACM Trans. Algorithms , 14(4):50:1--50:17

    2018

  29. [37]

    and Rousseeuw, P

    Kaufman, L. and Rousseeuw, P. J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis . John Wiley

    1990

  30. [38]

    Klein, P. N. and Young, N. E. (2015). On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. SIAM Journal on Computing , 44(4):1154--1172

    2015

  31. [39]

    and Munteanu, A

    Krivosija, A. and Munteanu, A. (2019). Probabilistic smallest enclosing ball in high dimensions via subgradient sampling. In International Symposium on Computational Geometry, (SoCG) , pages 47:1--47:14

    2019

  32. [40]

    Kuzilek, J., Hlosta, M., and Zdrahal, Z. (2017). Open University Learning Analytics Dataset . Scientific data , 4(1):1--8. https://doi.org/10.1038/sdata.2017.171

    2017 doi

  33. [41]

    Lemire, D. (2009). Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern Recognition , 42(9):2169--2180

    2009

  34. [42]

    Lopuha \"a , H. P. and Rousseeuw, P. J. (1991). Breakdown points of affine equivariant estimators of multivariate location and covariance matrices. The Annals of Statistics , pages 229--248

    1991

  35. [43]

    Luo, Y., Ke, W., Lam, C.-T., and Im, S.-K. (2024). An accurate slicing method for dynamic time warping algorithm and the segment-level early abandoning optimization. Knowledge-Based Systems , 300:1--16

    2024

  36. [44]

    Mai, T., Munteanu, A., Musco, C., Rao, A., Schwiegelshohn, C., and Woodruff, D. P. (2023). Optimal sketching bounds for sparse linear regression. In International Conference on Artificial Intelligence and Statistics, (AISTATS) , pages 11288--11316

    2023

  37. [45]

    Meintrup, S., Munteanu, A., and Rohde, D. (2019). Random projections and sampling algorithms for clustering of high-dimensional polygonal curves. In Proc. of the 32nd Conference on Neural Information Processing Systems ( NeurIPS ) , pages 12807--12817

    2019

  38. [46]

    Munteanu, A. (2023). Coresets and sketches for regression problems on data streams and distributed data. In Machine Learning under Resource Constraints, Volume 1 - Fundamentals , pages 85--98. De Gruyter, Berlin, Boston

    2023

  39. [47]

    and Omlor, S

    Munteanu, A. and Omlor, S. (2024). Turnstile _p leverage score sampling with applications. In 41st International Conference on Machine Learning, (ICML) , pages 36797--36828

    2024

  40. [48]

    Munteanu, A., Omlor, S., and Peters, C. (2022). p - G eneralized probit regression and scalable maximum likelihood estimation via sketching and coresets. In Proc. of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS) , pages 2073--2100

    2022

  41. [49]

    Munteanu, A., Omlor, S., and Woodruff, D. P. (2021). Oblivious sketching for logistic regression. In Proc. of the 38th International Conference on Machine Learning, (ICML) , pages 7861--7871

    2021

  42. [50]

    Munteanu, A., Omlor, S., and Woodruff, D. P. (2023). Almost linear constant-factor sketching for _1 and logistic regression. In The 11th International Conference on Learning Representations, (ICLR)

    2023

  43. [51]

    and Schwiegelshohn, C

    Munteanu, A. and Schwiegelshohn, C. (2018). Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms. K \" u nstliche Intell. , 32(1):37--53

    2018

  44. [52]

    and Nelson, J

    Narayanan, S. and Nelson, J. (2019). Optimal terminal dimensionality reduction in euclidean space. In Proc. of the 51st ACM Symposium on Theory of Computing, (STOC) , pages 1064--1069

    2019

  45. [53]

    Phillips, J. M. (2017). Coresets and sketches. In Handbook of Discrete and Computational Geometry , pages 1269--1288. Chapman and Hall/CRC, 3rd edition

    2017

  46. [54]

    Pisier, G. (1999). The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics. 94

    1999

  47. [55]

    and Rohde, D

    Psarros, I. and Rohde, D. (2023). Random projections for curves in high dimensions. In Proc. of the 39th International Symposium on Computational Geometry, (SoCG) , pages 53:1--53:15

    2023

  48. [56]

    and Chiba, S

    Sakoe, H. and Chiba, S. (1978). Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on acoustics, speech, and signal processing , 26(1):43--49

    1978

  49. [57]

    Silva, D. F. and Batista, G. E. A. P. A. (2016). Speeding up all-pairwise dynamic time warping matrix calculation. In Proc. of the 2016 SIAM International Conference on Data Mining, (SDM) , pages 837--845. SIAM

    2016

  50. [58]

    and Hwang, E

    Tak, Y.-S. and Hwang, E. (2007). A leaf image retrieval scheme based on partial dynamic time warping and two-level filtering. In 7th IEEE Conference on Computer and Information Technology (CIT) , pages 633--638

    2007

  51. [59]

    UIC , D. (2006). Real Trajectory Data . Databases and Mobile Computing Laboratory at University of Illinois at Chicago. https://www.cs.uic.edu/ boxu/mp2p/gps_data.html black https://www.cs.uic.edu/\ boxu/mp2p/gps\_data.html

    2006

  52. [60]

    Vintsyuk, T. K. (1968). Speech discrimination by dynamic programming. Cybernetics , 4(1):52--57

    1968

  53. [61]

    Williams, B. (2008). Character Trajectories . UCI Machine Learning Repository. https://doi.org/10.24432/C58G7V

    2008 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.