# Clustering time series under the Fr'echet distance

arXiv: https://arxiv.org/abs/1512.04349 · HTML: https://mlsanity.com/paper/1512.04349/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2015.

## Built on by (most cited first, 6 of 6)

- [StaDRe and StaDRo: Reliability and Robustness Estimation of ML-based Forecasting using Statistical Distance Measures](https://mlsanity.com/paper/2206.11116/) (2022)
- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [Classifying Spatial Trajectories](https://mlsanity.com/paper/2209.01322/) (2022)
- [Detection and Evaluation of Clusters within Sequential Data](https://mlsanity.com/paper/2210.01679/) (2022)
- [Measuring Time-Series Dataset Similarity using Wasserstein Distance](https://mlsanity.com/paper/2507.22189/) (2025)
- [Assessing Low Back Movement with Motion Tape Sensor Data Through Deep Learning](https://mlsanity.com/paper/2602.11465/) (2026)

## Abstract (arXiv)

The Fr'echet distance is a popular distance measure for curves. We study the problem of clustering time series under the Fr'echet distance. In particular, we give (1+varepsilon)-approximation algorithms for variations of the following problem with parameters k and ℓ. Given n univariate time series P, each of complexity at most m, we find k time series, not necessarily from P, which we call cluster centers and which each have complexity at most ℓ, such that (a) the maximum distance of an element of P to its nearest cluster center or (b) the sum of these distances is minimized. Our algorithms have running time near-linear in the input size for constant varepsilon, k and ℓ. To the best of our knowledge, our algorithms are the first clustering algorithms for the Fr'echet distance which achieve an approximation factor of (1+varepsilon) or better. Keywords: time series, longitudinal data, functional data, clustering, Fr'echet distance, dynamic time warping, approximation algorithms.