Clustering time series under the Fréchet distance

DOI10.1137/1.9781611974331.CH55MaRDI QIDQ4575634zbMATH OpenOpenAlexFDO

Authors Anne Driemel, Amer Krivošija, Christian Sohler

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.04349

zbMATH Keywords

approximation algorithmsclusteringdynamic time warpingFréchet distancefunctional datalongitudinal datatime series

Mathematics Subject Classification ID

Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

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.

Recommendations

• Clustering of interval time series
• Clustering and representation of time series. Application to dissimilarities based on divergences
• Clustering of time series data -- a survey
• Clustering multivariate time series using energy distance
• Time-series clustering
• Clustering discrete-valued time series
• Time-series clustering via quasi U-statistics
• Time series clustering and classification by the autoregressive metric
• Time series clustering in linear time complexity

Cited in

(25)

• Clustering and representation of time series. Application to dissimilarities based on divergences
• Clustering space-time series: FSTAR as a flexible STAR approach
• The VC dimension of metric balls under Fréchet and Hausdorff distances
• $k$-median clustering under discrete Fréchet and Hausdorff distances
• The VC dimension of metric balls under Fréchet and Hausdorff distances
• Temporal clustering
• Approximating \((k,\ell)\)-center clustering for curves
• scientific article; zbMATH DE number 7662168 (Why is no real title available?)
• Approximating ( k,ℓ )-Median Clustering for Polygonal Curves
• \(k\)-median clustering under discrete Fréchet and Hausdorff distances
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• (1+)-ANN data structure for curves via subspaces of bounded doubling dimension
• On computing exact means of time series using the move-split-merge metric
• Random projections for curves in high dimensions
• Faster Fréchet distance approximation through truncated smoothing
• Fast approximations and coresets for (k,)-median under dynamic time warping
• Random projections for curves in high dimensions
• Detection and evaluation of clusters within sequential data
• Revisiting the Fréchet distance between piecewise smooth curves
• A faster algorithm for the Fréchet distance in 1D for the imbalanced case
• Transforming dogs on the line: on the Fréchet distance under translation or scaling in 1D
• Simplification of trajectory streams
• Fréchet distance in unweighted planar graphs
• Probabilistic clustering of time-evolving distance data
• ANN for time series under the Fréchet distance

This page was built for publication: Clustering time series under the Fréchet distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575634)