2023/12/15 by Jacobus Conradi, Conradi, Jacobus, Benedikt Kolbe +5 · 1 citation
Computer Science · Engineering · #Automated Road and Building Extraction #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Gait Recognition and Analysis #Human Pose and Action Recognition
paper · pdf · doi:10.48550/arxiv.2312.09838
openalex publication_date 2023/12/15 · openalex created_date 2023/12/19 · openalex updated_date 2026/07/28
We present algorithms for the computation of ε-coresets for k-median clustering of point sequences in ℝd under the p-dynamic time warping (DTW) distance. Coresets under DTW have not been investigated before, and the analysis is not directly accessible to existing methods as DTW is not a metric. The three main ingredients that allow our construction of coresets are the adaptation of the ε-coreset framework of sensitivity sampling, bounds on the VC dimension of approximations to the range spaces of balls under DTW, and new approximation algorithms for the k-median problem under DTW. We achieve our results by investigating approximations of DTW that provide a trade-off between the provided accuracy and amenability to known techniques. In particular, we observe that given n curves under DTW, one can directly construct a metric that approximates DTW on this set, permitting the use of the wealth of results on metric spaces for clustering purposes. The resulting approximations are the first with polynomial running time and achieve a very similar approximation factor as state-of-the-art techniques. We apply our results to produce a practical algorithm approximating (k,ℓ)-median clustering under DTW.