TY - GEN

T1 - Dynamic L-Budget Clustering of Curves

AU - Buchin, Kevin

AU - Buchin, Maike

AU - Gudmundsson, Joachim

AU - Plätz, Lukas

AU - Thiel, Lea

AU - Wong, Sampson

N1 - Publisher Copyright: © Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Lukas Plätz, Lea Thiel, and Sampson Wong; licensed under Creative Commons License CC-BY 4.0.

PY - 2024/6

Y1 - 2024/6

N2 - A key goal of clustering is data reduction. In center-based clustering of complex objects therefore not only the number of clusters but also the complexity of the centers plays a crucial role. We propose LBudget Clustering as unifying perspective on this task, optimizing the clustering under the constraint that the summed complexity of all centers is at most L. We present algorithms for clustering planar curves under the Fréchet distance, but note that our algorithms more generally apply to objects in metric spaces if a notion of simplification of objects is applicable. A scenario in which data reduction is of particular importance is when the space is limited. Our main result is an efficient (8 + ε)-approximation algorithm with a (1 + ε)-resource augmentation that maintains an L-budget clustering under insertion of curves using only O(Lε−1) space and O∗(L3 log L + L2 log(r∗/r0)) time where O∗ hides factors of ε−1

AB - A key goal of clustering is data reduction. In center-based clustering of complex objects therefore not only the number of clusters but also the complexity of the centers plays a crucial role. We propose LBudget Clustering as unifying perspective on this task, optimizing the clustering under the constraint that the summed complexity of all centers is at most L. We present algorithms for clustering planar curves under the Fréchet distance, but note that our algorithms more generally apply to objects in metric spaces if a notion of simplification of objects is applicable. A scenario in which data reduction is of particular importance is when the space is limited. Our main result is an efficient (8 + ε)-approximation algorithm with a (1 + ε)-resource augmentation that maintains an L-budget clustering under insertion of curves using only O(Lε−1) space and O∗(L3 log L + L2 log(r∗/r0)) time where O∗ hides factors of ε−1

KW - approximation algorithms

KW - clustering

KW - Fréchet distance

KW - polygonal curves

KW - simplification

KW - storage efficiency

KW - streaming algorithm

U2 - 10.4230/LIPIcs.SWAT.2024.18

DO - 10.4230/LIPIcs.SWAT.2024.18

M3 - Article in proceedings

AN - SCOPUS:85195370407

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024

A2 - Bodlaender, Hans L.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024

Y2 - 12 June 2024 through 14 June 2024

ER -