English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present algorithms for the computation of $\varepsilon$-coresets for$k$-median clustering of point sequences in $\mathbb{R}^d$ under the$p$-dynamic time warping (DTW) distance. Coresets under DTW have not beeninvestigated before, and the analysis is not directly accessible to existingmethods as DTW is not a metric. The three main ingredients that allow ourconstruction of coresets are the adaptation of the $\varepsilon$-coresetframework of sensitivity sampling, bounds on the VC dimension of approximationsto the range spaces of balls under DTW, and new approximation algorithms forthe $k$-median problem under DTW. We achieve our results by investigatingapproximations of DTW that provide a trade-off between the provided accuracyand amenability to known techniques. In particular, we observe that given $n$curves under DTW, one can directly construct a metric that approximates DTW onthis set, permitting the use of the wealth of results on metric spaces forclustering purposes. The resulting approximations are the first with polynomialrunning time and achieve a very similar approximation factor asstate-of-the-art techniques. We apply our results to produce a practicalalgorithm approximating $(k,\ell)$-median clustering under DTW.

Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warping