Clustering time series under the Fréchet distance

A. Driemel; A. Krivosija; C. Sohler

Clustering time series under the Fréchet distance

A. Driemel, A. Krivosija, C. Sohler

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

50 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 language	English
Title of host publication	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Publisher	Association for Computing Machinery, Inc.
Pages	766-785
Number of pages	20
Volume	2
ISBN (Electronic)	9781510819672
Publication status	Published - 2016
Event	27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) - Arlington, United States Duration: 10 Jan 2016 → 12 Jan 2016 Conference number: 27 http://www.siam.org/meetings/da16/

Conference

Conference	27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
Abbreviated title	SODA2016
Country/Territory	United States
City	Arlington
Period	10/01/16 → 12/01/16
Internet address	http://www.siam.org/meetings/da16/

Keywords

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

Cite this

@inproceedings{e02393d448cb4c7f96561553724cc29c,

title = "Clustering time series under the Fr{\'e}chet distance",

abstract = "The Fr{\'e}chet distance is a popular distance measure for curves. We study the problem of clustering time series under the Fr{\'e}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{\'e}chet distance which achieve an approximation factor of (1 + ∈) or better.",

keywords = "Approximation algorithms, Chet distance, Clustering, Dynamic time warping, Fr{\'e}, Functional data, Longitudinal data, Time series",

author = "A. Driemel and A. Krivosija and C. Sohler",

year = "2016",

language = "English",

volume = "2",

pages = "766--785",

booktitle = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016",

publisher = "Association for Computing Machinery, Inc.",

address = "United States",

note = "27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), SODA2016 ; Conference date: 10-01-2016 Through 12-01-2016",

url = "http://www.siam.org/meetings/da16/",

}

TY - GEN

T1 - Clustering time series under the Fréchet distance

AU - Driemel, A.

AU - Krivosija, A.

AU - Sohler, C.

N1 - Conference code: 27

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Chet distance

KW - Clustering

KW - Dynamic time warping

KW - Fré

KW - Functional data

KW - Longitudinal data

KW - Time series

UR - http://www.scopus.com/inward/record.url?scp=84963679856&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84963679856

VL - 2

SP - 766

EP - 785

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

PB - Association for Computing Machinery, Inc.

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

Y2 - 10 January 2016 through 12 January 2016

ER -

Clustering time series under the Fréchet distance

Abstract

Conference

Keywords

Other files and links

Fingerprint

Cite this