Pith. sign in

REVIEW 4 minor 60 references

Terminal embeddings can be extended from points to line segments, yielding the first dimension-free coresets for Fréchet clustering of time series.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review

2026-07-13 02:38 UTC pith:34QWFZ65

load-bearing objection First terminal embeddings that multiplicatively preserve continuous Fréchet distance on affine lines, yielding the first dimension-free coresets of near-optimal size for (k,ℓ,z)-clustering of polygonal curves.

arxiv 2607.09490 v1 pith:34QWFZ65 submitted 2026-07-10 cs.DS cs.CGcs.LGstat.ML

Terminal Dimension Reduction for Time Series with Applications

Alexander Munteanu , Matteo Russo , David Saulpic , Chris Schwiegelshohn This is my paper
classification cs.DS cs.CGcs.LGstat.ML MSC 68W2568U0552C45
keywords terminal embeddingsFréchet distancecoresetstime seriesdimension reductionpolygonal curvesJohnson-Lindenstrauss
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Terminal embeddings preserve distances from a fixed finite set of points to every possible query point in the ambient space; they have been the key tool for building dimension-independent coresets for ordinary k-means and k-median. Time-series data, however, are polygonal curves whose straight-line segments are infinite linear structures, and classical terminal maps cannot be linear. The paper constructs a new, piecewise-linear terminal embedding that simultaneously preserves distances from every point on every input segment to every point on every query line. Once such maps exist, standard coreset frameworks immediately produce the first coresets for continuous Fréchet clustering whose size is completely independent of ambient dimension. The resulting size is essentially optimal for constant-complexity curves, recovering the known lower bounds for ordinary point clustering.

Core claim

There exist (ε,m,ℓ)-preserving terminal embeddings for the Fréchet distance whose target dimension is O(ℓ ε^{-4} log(nm)). These embeddings yield the first dimension-free ε-coresets of size Õ(k ε^{-2-z} ℓ² log² m) for (k,ℓ,z)-clustering of polygonal curves under continuous Fréchet distance.

What carries the argument

A covering lemma that, for any fixed collection of query lines, selects O(ℓ ε^{-2}) input segments whose span approximately contains every query direction; residual orthogonal components are then stored in a constant number of ancillary coordinates, after which a single Johnson-Lindenstrauss sketch preserves all remaining distances.

Load-bearing premise

The covering argument produces only O(1/ε²) segments per query line and the subsequent union bound over exponentially many candidate subspaces remains valid at the stated dimension.

What would settle it

Exhibit a concrete family of n curves of complexity m for which every map that multiplicatively preserves Fréchet distances to all complexity-ℓ queries requires target dimension ω(ℓ ε^{-4} log(nm)), or produce a coreset lower bound that exceeds Õ(k ε^{-2-z} ℓ² log² m).

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper constructs terminal embeddings that preserve Fréchet distances between input polygonal curves of complexity m and arbitrary query curves of complexity ℓ, with target dimension O(ℓ ε^{-4} log(nm)) (Theorem 1.2). The construction proceeds by a greedy residual covering (Lemma 3.1) that produces a low-dimensional projection Π onto O(ℓ ε^{-2}) input segments, followed by a subspace-preserving sketch and a constant number of ancillary coordinates; the same covering yields an approximate-centroid-set enumeration that, when fed into a refined chaining analysis of the Cohen-Addad et al. (2021) framework, produces the first dimension-free coresets of size Õ(k ε^{-2-z} ℓ^{2} log^{2} m) for (k,ℓ,z)-clustering under Fréchet distance (Theorem 1.3). Experiments on synthetic and real GHG time series illustrate that the embeddings behave comparably to plain JL and better than PCA while uniquely extending preservation to ambient queries.

Significance. Terminal embeddings have been indispensable for dimension-free coresets of Euclidean k-means/median, yet they are inherently non-linear and therefore previously unavailable for continuous Fréchet clustering of polygonal curves. The paper supplies the missing geometric primitive—an explicit, piecewise-linear terminal embedding for affine line segments—and immediately obtains the first coresets whose size is independent of ambient dimension d. The resulting bound recovers the optimal point-clustering dependence on k and ε whenever ℓ and m are constant, and the construction re-uses only standard subspace sketches and the existing coreset framework, so the advance is cleanly modular. The experimental section, while only illustrative, confirms that the extra orthogonal-projection error remains a small constant factor, supporting practical utility.

minor comments (4)
  1. In the proof of Theorem 1.2 the final rescaling of ε by a factor 3 is stated without an explicit intermediate inequality; a short display of the (1±ε)^{2} accumulation would improve readability.
  2. Proposition 3.4 quotes a running time O(nmd ℓ^{2} ε^{-6} log(nm)) for pre-computing g; a parenthetical remark that sparse JL matrices improve the ε dependence would be helpful for implementers.
  3. Table 1 lists previous coreset sizes; adding a column that isolates the dependence on d would make the dimension-free improvement more immediately visible.
  4. The experimental figure caption should state the number of independent random projections used for each box-plot so that variance can be assessed.

Circularity Check

0 steps flagged

No significant circularity: terminal embeddings and coresets are derived constructively from external JL/subspace sketches and a refined external coreset framework, with no fitted parameters or definitional loops.

full rationale

The load-bearing claims (Thm 1.2 terminal embeddings via Lemmas 3.1–3.2 + Cor 3.3 + subspace sketches of Lem 2.1; Thm 1.3 coresets via the chaining framework of Thm C.3 + explicit centroid-set construction of Lem C.4) are proved from first principles inside the paper or by black-box invocation of external results (Woodruff 2014 subspace sketches; Cohen-Addad et al. 2021 coreset framework). The covering size O(|S|ε^{-2}) follows from a greedy residual argument + Pythagorean theorem (explicitly proved); the exponential net of projections is enumerated combinatorially from nm segments; the target dimension absorbs the union bound. The coreset analysis re-derives the chaining argument self-containedly in App D and supplies the missing Fréchet centroid set; prior coreset papers by overlapping authors are used only as the starting framework that is improved, not as an unverified uniqueness theorem that forces the result. Experiments are purely illustrative (free target dimensions) and do not enter the asymptotic claims. No self-definitional loop, no fitted-to-predicted quantity, and no ansatz smuggled via citation appear.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 2 invented entities

The paper rests on classical random-projection lemmas, the definition of continuous Fréchet distance, and the existence of approximate centroid sets / chaining nets from prior coreset papers. The only genuinely new objects are the line-covering projection Π and the piecewise-linear terminal map built from it; everything else is imported.

axioms (3)
  • standard math Subspace-preserving sketches (Lemma 2.1 / Woodruff 2014): a random r×d matrix with r = O(ε^{-2}(j+log(1/δ))) multiplies any fixed j-dimensional orthonormal matrix by (1±ε) in spectral norm with probability 1-δ.
    Invoked for every candidate projection Π and every input segment; the target dimension is set by a union bound over exp(O(ℓ ε^{-2} log(nm))) many subspaces.
  • domain assumption The continuous Fréchet distance is a metric on the space of polygonal curves of bounded complexity.
    Used throughout to guarantee that preserving all pointwise distances implies preservation of the inf-sup reparameterization distance.
  • domain assumption Existence of (α,k,z,A)-approximate centroid sets of size exp(O(ℓ(k log(nm)+k d log(ℓ/α)))) for Fréchet clustering (Lemma C.4).
    Taken from the Cohen-Addad et al. framework and specialized to curves; the terminal embedding is then used only to replace d by the reduced dimension.
invented entities (2)
  • (ε,m,ℓ)-preserving terminal embedding for Fréchet distance no independent evidence
    purpose: Map that simultaneously preserves distances from every point on every input segment to every point on every affine line of a query curve of complexity ≤ℓ.
    The central technical object; constructed via the covering of Lemma 3.1 plus JL plus 2ℓ ancillary coordinates. No independent experimental or formal verification outside the paper.
  • Projection matrix Π onto O(ℓ ε^{-2}) input segments satisfying the residual-inner-product bound of Lemma 3.2 no independent evidence
    purpose: Reduces the multiplicative-error problem for an arbitrary query line to a low-dimensional subspace plus an orthogonal remainder that can be stored in ancillary coordinates.
    Obtained by the greedy covering of Lemma 3.1; size and existence are proved inside the paper only.

reviewed 2026-07-13 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Terminal Dimension Reduction for Time Series with Applications." pith.science (2026). https://pith.science/paper/34QWFZ65

@misc{pith2026260709490,
  author       = {Pith},
  title        = {Pith review of: Terminal Dimension Reduction for Time Series with Applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/34QWFZ65}},
  note         = {Machine review of arXiv:2607.09490}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Terminal embeddings have emerged as a powerful tool for dimension reduction. Given a set of points $P\subset \mathbb{R}^d$, a terminal embedding is a mapping $f:\mathbb{R}^d\rightarrow \mathbb{R}^t$ that preserves the pairwise distance between any pair of points $p\in P$ and $q\in \mathbb{R}^d$ up to small distortion under this mapping. Terminal embeddings have been particularly fruitful for constructing $k$-means and $k$-median coresets, where the objective is to find a typically weighted subset $\Omega$ of $P$ such that for any candidate solution, the cost of the clustering objective on $\Omega$ approximates the cost of the clustering objective on $P$ up to small distortion. Unfortunately, these techniques have not been extended to more complicated structures such as clustering time-series data under common straight-line interpolation between measurements. The main issue is that terminal embeddings, arguably the central technique in this line of research, cannot be linear and are thus not immediately suitable to preserve linear structures. In this work, we develop a generalization of terminal embeddings to affine line-segments that overcomes this issue. We showcase their applicability by using our lines-preserving terminal embeddings to obtain the first dimension-free coresets for clustering time-series under the Fr\'echet distance. The underlying dimension reduction uses Johnson-Lindenstrauss (JL) embeddings, and our experiments indicate that terminal embeddings perform similarly to JL and favorably against PCA for synthetic and real-world time-series, while only terminal embeddings extend pairwise distance preservation to the full ambient space.

Figures

Figures reproduced from arXiv: 2607.09490 by Alexander Munteanu, Chris Schwiegelshohn, David Saulpic, Matteo Russo.

Figure 1
Figure 1. Figure 1: Comparison of the approximation ratios (lower is better) of 120 Fréchet distances between time-series, [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the natural conditions. s min is the top segment, s the lower one. Proof. By the parameterization chosen above, it holds that ∥p min(t) − γ(t)∥ ≤ dF (p min, γ) ≤ 8∆ α and ∥p(t) − γ(t)∥ ≤ dF (p, γ) ≤ 25∆ α2 . We conclude with triangle inequality. Let γe 1 v be a vertex not in any ball B(p i j , ℓ · 100∆α −2 ), and let t be such that γe 1 (t) = γe 1 v = γv. Let s min be the segment of p min t… view at source ↗
Figure 3
Figure 3. Figure 3: Proof overview of the coreset construction framework guarantee: Theorem [PITH_FULL_IMAGE:figures/full_fig_p034_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: We plot the sample rings for A = {c1, c2, c3} in which cost(C1) = cost(C2) < cost(C3). We have labeled the rings R1j , R2j and R3j for j = 1 – note that the width of each ring is proportional to the cost of its cluster. Now let us assume that R1j and R3j have equal densities of points but that R2j has higher density (as evidenced by the shading). Then we might have Gjb = R1j and Gjb′ = R2j ∪ R3j for b ′ > … view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 14 canonical work pages · 1 internal anchor

  1. [1]

    Optimal compression of approximate inner products and dimension reduction

    Noga Alon and Bo'az Klartag. Optimal compression of approximate inner products and dimension reduction. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 639--650. IEEE Computer Society, 2017. URL https://doi.org/10.1109/FOCS.2017.65

    work page doi:10.1109/focs.2017.65 2017

  2. [2]

    Fr \'e chet distance for curves, revisited

    Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fr \'e chet distance for curves, revisited. In European symposium on algorithms (ESA) , pages 52--63. Springer, 2006. URL http://doi.org/10.1007/11841036_8

    work page doi:10.1007/11841036_8 2006

  3. [3]

    Sensitivity sampling for k-means: worst case and stability optimal coreset bounds

    Nikhil Bansal, Vincent Cohen - Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: worst case and stability optimal coreset bounds. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 , pages 1707--1723. IEEE , 2024. URL https://doi.org/10.1109/FOCS...

    doi:10.1109/focs61266.2024.00106 2024

  4. [4]

    Oblivious dimension reduction for k-means: beyond subspaces and the J ohnson- L indenstrauss lemma

    Luca Becchetti, Marc Bury, Vincent Cohen - Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the J ohnson- L indenstrauss lemma. In Symposium on Theory of Computing, STOC , pages 1039--1050, 2019. URL https://doi.org/10.1145/3313276.3316318

    doi:10.1145/3313276.3316318 2019

  5. [5]

    Vladimir Braverman, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In D \' a niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 , pages 2679--2696. SIAM , 2021. URL https://doi.org/10.1137/1.9781611...

    doi:10.1137/1.9781611976465.159 2021

  6. [6]

    Vladimir Braverman, Vincent Cohen - Addad, Shaofeng H. - C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 462--473. IEEE , 2022. URL https://doi.o...

    doi:10.1109/focs54457.2022.00051 2022

  7. [7]

    Simplified and Improved Bounds on the VC-Dimension for Elastic Distance Measures

    Frederik Br \" u ning and Anne Driemel. Simplified and improved bounds on the VC -dimension for elastic distance measures. CoRR, abs/2308.05998, 2023. URL https://doi.org/10.48550/arXiv.2308.05998

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2308.05998 2023

  8. [8]

    On generalization bounds for projective clustering

    Maria Sofia Bucarelli, Matilde Fjelds Larsen, Chris Schwiegelshohn, and Mads Toftrup. On generalization bounds for projective clustering. In Advances in Neural Information Processing Systems, (NeurIPS) , pages 71723--71754, 2023

    2023

  9. [9]

    Coresets for (k, ) -median clustering under the F r \' e chet distance

    Maike Buchin and Dennis Rohde. Coresets for (k, ) -median clustering under the F r \' e chet distance. In Niranjan Balachandran and R. Inkulu, editors, Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Puducherry, India, February 10-12, 2022, Proceedings , volume 13179 of Lecture Notes in Computer Science, pages 167-...

    doi:10.1007/978-3-030-95018-7 2022

  10. [10]

    Approximating ( k, \( l \) )-median clustering for polygonal curves

    Maike Buchin, Anne Driemel, and Dennis Rohde. Approximating ( k, \( l \) )-median clustering for polygonal curves. ACM Trans. Algorithms , 19 0 (1): 0 4:1--4:32, 2023. URL https://doi.org/10.1145/3559764

    doi:10.1145/3559764 2023

  11. [11]

    Augmented functional time series representation and forecasting with gaussian processes

    Nicolas Chapados and Yoshua Bengio. Augmented functional time series representation and forecasting with gaussian processes. In Advances in Neural Information Processing Systems 20, pages 265--272. , 2008

    2008

  12. [12]

    Optimal embedding dimension for sparse subspace embeddings

    Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, and Mark Rudelson. Optimal embedding dimension for sparse subspace embeddings. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 , pages 1106--1117. ACM , 2024. URL https://do...

    doi:10.1145/3618260.3649762 2024

  13. [13]

    Curve simplification and clustering under fr \' e chet distance

    Siu - Wing Cheng and Haoqiang Huang. Curve simplification and clustering under fr \' e chet distance. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 1414--1432. SIAM , 2023. URL https://doi.org/10.1137/1.9781611977554.ch51

    doi:10.1137/1.9781611977554.ch51 2023

  14. [14]

    Solving F r \' e chet distance problems by algebraic geometric methods

    Siu - Wing Cheng and Haoqiang Huang. Solving F r \' e chet distance problems by algebraic geometric methods. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 4502--4513. SIAM , 2024. URL https://doi.org/10.1137/1.9781611977912.158

    work page doi:10.1137/1.9781611977912.158 2024

  15. [15]

    Terminal embeddings in sublinear time

    Yeshwanth Cherapanamjeri and Jelani Nelson. Terminal embeddings in sublinear time. TheoretiCS, 3, 2024. URL https://doi.org/10.46298/theoretics.24.6

    work page doi:10.46298/theoretics.24.6 2024

  16. [16]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 , pages 205--214. ACM , 2009. URL https://doi.org/10.1145/1536414.1536445

    doi:10.1145/1536414.1536445 2009

  17. [17]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 81--90. ACM , 2013. URL https://doi.org/10.1145/2488608.2488620

    doi:10.1145/2488608.2488620 2013

  18. [18]

    Michael B. Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 , pages 278--287. SIAM , 2016. URL https://doi.org/10.1137/1.9781611974331.ch21

    doi:10.1137/1.9781611974331.ch21 2016

  19. [19]

    A new coreset framework for clustering

    Vincent Cohen - Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 169--182. ACM , 2021. URL https://doi.org/10.1145/3406325.3451022

    doi:10.1145/3406325.3451022 2021

  20. [20]

    Towards optimal lower bounds for k -median and k -means coresets

    Vincent Cohen - Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k -median and k -means coresets. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 1038--1051. ACM , 2022 a . URL https://doi.org/10.11...

    doi:10.1145/3519935.3519946 2022

  21. [21]

    Improved coresets for E uclidean k-means

    Vincent Cohen - Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh - Omar. Improved coresets for E uclidean k-means. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022,...

    2022

  22. [22]

    Deterministic clustering in high dimensional spaces: sketches and approximation

    Vincent Cohen - Addad, David Saulpic, and Chris Schwiegelshohn. Deterministic clustering in high dimensional spaces: sketches and approximation. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 1105--1130. IEEE , 2023. URL https://doi.org/10.1109/FOCS57990.2023.00066

    doi:10.1109/focs57990.2023.00066 2023

  23. [23]

    A tight VC -dimension analysis of clustering coresets with applications

    Vincent Cohen - Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. A tight VC -dimension analysis of clustering coresets with applications. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 , pages 4783--4...

    doi:10.1137/1.9781611978322.162 2025

  24. [24]

    Almost optimal PAC learning for k-means

    Vincent Cohen - Addad, Silvio Lattanzi, and Chris Schwiegelshohn. Almost optimal PAC learning for k-means. In Michal Kouck \' y and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025 , pages 2019--2030. ACM , 2025 b . doi:10.1145/3717823.3718180. URL https://doi.org/10....

    doi:10.1145/3717823.3718180 2025

  25. [25]

    Fast approximations and coresets for (k, ) -median under dynamic time warping

    Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde. Fast approximations and coresets for (k, ) -median under dynamic time warping. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 42:1--42:17. Schloss Dagstuhl -...

    doi:10.4230/lipics.socg.2024.42 2024

  26. [26]

    Probabilistic embeddings of the F r \' e chet distance

    Anne Driemel and Amer Krivosija. Probabilistic embeddings of the F r \' e chet distance. In Leah Epstein and Thomas Erlebach, editors, Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers , volume 11312 of Lecture Notes in Computer Science, pages 218--237. Springer, 20...

    doi:10.1007/978-3-030-04693-4 2018

  27. [27]

    Clustering time series under the F r \' e chet distance

    Anne Driemel, Amer Krivosija, and Christian Sohler. Clustering time series under the F r \' e chet distance. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 , pages 766--785. SIAM , 2016. URL https://doi.org/10.1137/1.9781611974331.ch55

    doi:10.1137/1.9781611974331.ch55 2016

  28. [28]

    Phillips, and Ioannis Psarros

    Anne Driemel, Andr \' e Nusser, Jeff M. Phillips, and Ioannis Psarros. The VC dimension of metric balls under F r \' e chet and H ausdorff distances. Discrete and Computational Geometry, 66 0 (4): 0 1351--1381, 2021. URL https://doi.org/10.1007/s00454-021-00318-z

    work page doi:10.1007/s00454-021-00318-z 2021

  29. [29]

    Terminal embeddings

    Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. Theor. Comput. Sci., 697: 0 1--36, 2017. URL https://doi.org/10.1016/j.tcs.2017.06.021

    work page doi:10.1016/j.tcs.2017.06.021 2017

  30. [30]

    Core-sets: An updated survey

    Dan Feldman. Core-sets: An updated survey. WIREs Data Mining Knowl. Discov., 10 0 (1), 2020. doi:10.1002/WIDM.1335. URL https://doi.org/10.1002/widm.1335

    doi:10.1002/widm.1335 2020

  31. [31]

    Sparse dimensionality reduction revisited

    Mikael M ller H gsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, and Chris Schwiegelshohn. Sparse dimensionality reduction revisited. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 . OpenReview.net, 2024. URL https://openreview.net/forum?id=ufgVvFmUom

    2024

  32. [32]

    Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in E uclidean spaces: importance sampling is nearly optimal. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 , pages...

    doi:10.1145/3357713.3384296 2020

  33. [33]

    Sudhir, and Nisheeth K

    Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. Coresets for regressions with panel data. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria - Florina Balcan, and Hsuan - Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020...

    2020

  34. [34]

    Sudhir, and Nisheeth K

    Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. Coresets for time series clustering. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, v...

    2021

  35. [35]

    On optimal coreset construction for E uclidean (k, z) -clustering

    Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for E uclidean (k, z) -clustering. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 , pages 1594--1604. ACM , 2024. URL https://doi.org/10.1145/3618260.3649707

    doi:10.1145/3618260.3649707 2024

  36. [36]

    Extensions of Lipschitz mappings into a Hilbert space

    William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability, volume 26, pages 189--206. American Mathematical Society, 1984

    1984

  37. [37]

    Kane and Jelani Nelson

    Daniel M. Kane and Jelani Nelson. Sparser J ohnson- L indenstrauss transforms. J. ACM , 61 0 (1): 0 4:1--4:23, 2014. URL https://doi.org/10.1145/2559902

    doi:10.1145/2559902 2014

  38. [38]

    Improved learning via k-dtw: A novel dissimilarity measure for curves

    Amer Krivosija, Alexander Munteanu, Andr \' e Nusser, and Chris Schwiegelshohn. Improved learning via k-dtw: A novel dissimilarity measure for curves. In Forty-second International Conference on Machine Learning (ICML), 2025. URL https://openreview.net/forum?id=VCjPjexvpM

    2025

  39. [39]

    Optimality of the J ohnson- L indenstrauss lemma

    Kasper Green Larsen and Jelani Nelson. Optimality of the J ohnson- L indenstrauss lemma. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 633--638. IEEE Computer Society, 2017. URL https://doi.org/10.1109/FOCS.2017.64

    work page doi:10.1109/focs.2017.64 2017

  40. [40]

    D. D. Lucas, C. Yver Kwok, P. Cameron-Smith, H. Graven, D. Bergmann, T. P. Guilderson, R. Weiss, and R. Keeling. Designing optimal greenhouse gas observing networks that consider performance and cost. Geoscientific Instrumentation, Methods and Data Systems, 4 0 (1): 0 121--137, 2015. doi:10.5194/gi-4-121-2015. URL https://www.geosci-instrum-method-data-sy...

    work page doi:10.5194/gi-4-121-2015 2015

  41. [41]

    Razenshteyn

    Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Nonlinear dimension reduction via outer B i- L ipschitz extensions. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 , pages 1088-...

    work page doi:10.1145/3188745.3188828 2018

  42. [42]

    Razenshteyn

    Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of J ohnson- L indenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 1027--1038, 2019. URL https://doi.org/10.1145/3313276.3316350

    doi:10.1145/3313276.3316350 2019

  43. [43]

    Exponential and Information Inequalities, chapter 2, pages 15--51

    Pascal Massart. Exponential and Information Inequalities, chapter 2, pages 15--51. Springer Berlin Heidelberg, 2007

    2007

  44. [44]

    Random projections and sampling algorithms for clustering of high-dimensional polygonal curves

    Stefan Meintrup, Alexander Munteanu, and Dennis Rohde. Random projections and sampling algorithms for clustering of high-dimensional polygonal curves. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch \' e - Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neur...

    2019

  45. [45]

    Xiangrui Meng and Michael W. Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 91--100. ACM , 2013. URL https://doi.org/10.1145/2488608.2488621

    doi:10.1145/2488608.2488621 2013

  46. [46]

    Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms

    Alexander Munteanu and Chris Schwiegelshohn. Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms. K \" u nstliche Intell. , 32 0 (1): 0 37--53, 2018. URL https://doi.org/10.1007/s13218-017-0519-3

    doi:10.1007/s13218-017-0519-3 2018

  47. [47]

    Optimal terminal dimensionality reduction in E uclidean space

    Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in E uclidean space. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 1064--1069. ACM , 2019. URL https://doi.org/10.1145/3313276.3316307

    doi:10.1145/3313276.3316307 2019

  48. [48]

    Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings

    Jelani Nelson and Huy L Nguy \^e n. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS , 2013

    2013

  49. [49]

    Bridging the gap: A decade review of time-series clustering methods

    John Paparrizos, Fan Yang, and Haojun Li. Bridging the gap: A decade review of time-series clustering methods. CoRR, abs/2412.20582, 2024. doi:10.48550/ARXIV.2412.20582. URL https://doi.org/10.48550/arXiv.2412.20582

    Pith/arXiv arXiv doi:10.48550/arxiv.2412.20582 2024

  50. [50]

    Karl Pearson. LIII . on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2 0 (11): 0 559--572, 1901. doi:10.1080/14786440109462720. URL https://doi.org/10.1080/14786440109462720

    doi:10.1080/14786440109462720 1901

  51. [51]

    Random projections for curves in high dimensions

    Ioannis Psarros and Dennis Rohde. Random projections for curves in high dimensions. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA , volume 258 of LIPIcs, pages 53:1--53:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. URL https:...

    doi:10.4230/lipics.socg.2023.53 2023

  52. [52]

    Random projections for curves in high dimensions

    Ioannis Psarros and Dennis Rohde. Random projections for curves in high dimensions. Discret. Comput. Geom., 74 0 (2): 0 374--398, 2025. URL https://doi.org/10.1007/s00454-024-00710-5

    doi:10.1007/s00454-024-00710-5 2025

  53. [53]

    Every list-decodable code for high noise has abundant near-optimal rate puncturings

    Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 , pages 764--773. ACM , 2014. URL https://doi.org/10.1145/2591796.2591797

    work page doi:10.1145/2591796.2591797 2014

  54. [54]

    Improved approximation algorithms for large matrices via random projections

    Tam \' a s Sarl \' o s. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings , pages 143--152. IEEE Computer Society, 2006. URL https://doi.org/10.1109/FOCS.2006.37

    doi:10.1109/focs.2006.37 2006

  55. [55]

    Majorizing measures: The generic chaining

    Michel Talagrand. Majorizing measures: The generic chaining. The Annals of Probability, 24 0 (3): 0 1049--1103, 1996. ISSN 00911798, 2168894X. URL http://www.jstor.org/stable/2244967

    arXiv 1996

  56. [56]

    Mengyu Wang, Tiejun Ma, and Shay B. Cohen. Pre-training time series models with stock data customization. In Luiza Antonie, Jian Pei, Xiaohui Yu, Flavio Chierichetti, Hady W. Lauw, Yizhou Sun, and Srinivasan Parthasarathy, editors, Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, V.2, KDD 2025, Toronto ON, Canada, Augu...

    work page doi:10.1145/3711896.3737005 2025

  57. [57]

    Woodruff

    David P. Woodruff. Sketching as a T ool for N umerical L inear A lgebra. Found. Trends Theor. Comput. Sci., 10 0 (1-2): 0 1--157, 2014. URL https://doi.org/10.1561/0400000060

    doi:10.1561/0400000060 2014

  58. [58]

    Anomaly detection in MODIS land products via time series analysis

    Jingxiong Zhang, David Roy, Sadashiva Devadiga, and Min Zheng. Anomaly detection in MODIS land products via time series analysis. Geo-spatial Information Science, 10 0 (1): 0 44--50, Mar 2007. ISSN 1993-5153. doi:10.1007/s11806-007-0003-6. URL https://doi.org/10.1007/s11806-007-0003-6

    work page doi:10.1007/s11806-007-0003-6 2007

  59. [59]

    Space complexity of E uclidean clustering

    Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang. Space complexity of E uclidean clustering. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 82:1--82:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024...

    work page doi:10.4230/lipics.socg.2024.82 2024

  60. [60]

    Safe active learning for time-series modeling with gaussian processes

    Christoph Zimmer, Mona Meister, and Duy Nguyen-Tuong. Safe active learning for time-series modeling with gaussian processes. In Advances in Neural Information Processing Systems 31, pages 2730--2739. , 2018

    2018

This paper was first reviewed by grok-4.5 on July 13, 2026.