Clustering time series under the Fréchet distance

A. Driemel, A. Krivosija, C. Sohler

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

45 Citaten (Scopus)
8 Downloads (Pure)


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.

Originele taal-2Engels
Titel27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
UitgeverijAssociation for Computing Machinery, Inc
Aantal pagina's20
ISBN van elektronische versie9781510819672
StatusGepubliceerd - 2016
Evenement27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) - Arlington, Verenigde Staten van Amerika
Duur: 10 jan. 201612 jan. 2016
Congresnummer: 27


Congres27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
Verkorte titelSODA2016
Land/RegioVerenigde Staten van Amerika
Internet adres


Duik in de onderzoeksthema's van 'Clustering time series under the Fréchet distance'. Samen vormen ze een unieke vingerafdruk.

Citeer dit