# Coresets for Time Series Clustering

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 63 references that are in the map.
- First posted on arXiv 28 Oct 2021.

## Builds on (most cited first, 13 of 13)

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [Fair and Diverse DPP-based Data Summarization](https://mlsanity.com/paper/1802.04023/) (2018)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Coresets for Regressions with Panel Data](https://mlsanity.com/paper/2011.00981/) (2020)
- [Coresets for Gaussian Mixture Models of Any Shape](https://mlsanity.com/paper/1906.04895/) (2019)

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Learning Mixtures of Markov Chains and MDPs](https://mlsanity.com/paper/2211.09403/) (2022)
- [QCore: Data-Efficient, On-Device Continual Calibration for Quantized Models -- Extended Version](https://mlsanity.com/paper/2404.13990/) (2024)
- [Representative Subset Selection for Efficient Fine-Tuning in Self-Supervised Speech Recognition](https://mlsanity.com/paper/2203.09829/) (2022)
- [Emulating Full Participation: An Effective and Fair Client Selection Strategy for Federated Learning](https://mlsanity.com/paper/2405.13584/) (2024)
- [Improved Coresets for Euclidean k-Means](https://mlsanity.com/paper/2211.08184/) (2022)
- [Coresets for Clustering Under Stochastic Noise](https://mlsanity.com/paper/2510.23438/) (2025)

## Abstract (arXiv)

We study the problem of constructing coresets for clustering problems with time series data. This problem has gained importance across many fields including biology, medicine, and economics due to the proliferation of sensors facilitating real-time measurement and rapid drop in storage costs. In particular, we consider the setting where the time series data on N entities is generated from a Gaussian mixture model with autocorrelations over k clusters in ℝd. Our main contribution is an algorithm to construct coresets for the maximum likelihood objective for this mixture model. Our algorithm is efficient, and under a mild boundedness assumption on the covariance matrices of the underlying Gaussians, the size of the coreset is independent of the number of entities N and the number of observations for each entity, and depends only polynomially on k, d and 1/varepsilon, where varepsilon is the error parameter. We empirically assess the performance of our coreset with synthetic data.