Dynamic L-Budget Clustering of Curves
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Dynamic L-Budget Clustering of Curves. / Buchin, Kevin; Buchin, Maike; Gudmundsson, Joachim; Plätz, Lukas; Thiel, Lea; Wong, Sampson.
19th Scandinavian Symposium on Algorithm Theory, SWAT 2024. red. / Hans L. Bodlaender. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024. 18 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 294).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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 -
ID: 395153652