• German

Main Navigation

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

Bibtype Inproceedings
Bibkey Driemel/2016a
Author Driemel, Anne and Krivo\v{s}ija, 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.