• German
German

Main Navigation

Driemel/2016a: Clustering time series under the Fr\'echet distance

Bibtype Inproceedings
Bibkey Driemel/2016a
Author Driemel, Anne and Krivosija, Amer and Sohler, Christian
Editor Krauthgamer, Robert
Title Clustering time series under the Fr\'echet distance
Booktitle Proceedings of the 27th Symposium on Discrete Algorithms (SODA)
Pages 766-785
Publisher SIAM
Abstract 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 $\ell$. Given $n$ univariate time series $P$, each of complexity at most $m$, we find $k$ time series, not necessarily from $P$, which we call \emph{cluster centers} and which each have complexity at most $\ell$, 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 $\ell$. 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.
Year 2016
Projekt SFB876-A2
Url http://epubs.siam.org/doi/10.1137/1.9781611974331.ch55
Bibtex Here you can get this literature entry as BibTeX format.