Clustering time series under the Fréchet distance

A. Driemel, A. Krivosija, C. Sohler

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

43 Citations (Scopus)
8 Downloads (Pure)

Abstract

The Fréchet distance is a popular distance measure for curves. We study the problem of clustering time series under the Fréchet distance. In particular, we give (1 + ∈)-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 ∈, k and ℓ. To the best of our knowledge, our algorithms are the first clustering algorithms for the Fréchet distance which achieve an approximation factor of (1 + ∈) or better.

Original languageEnglish
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
PublisherAssociation for Computing Machinery, Inc
Pages766-785
Number of pages20
Volume2
ISBN (Electronic)9781510819672
Publication statusPublished - 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) - Arlington, United States
Duration: 10 Jan 201612 Jan 2016
Conference number: 27
http://www.siam.org/meetings/da16/

Conference

Conference27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
Abbreviated titleSODA2016
Country/TerritoryUnited States
CityArlington
Period10/01/1612/01/16
Internet address

Keywords

  • Approximation algorithms
  • Chet distance
  • Clustering
  • Dynamic time warping
  • Fré
  • Functional data
  • Longitudinal data
  • Time series

Fingerprint

Dive into the research topics of 'Clustering time series under the Fréchet distance'. Together they form a unique fingerprint.

Cite this