2026-07-26T03:15:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17022 2024-03-06T10:58:59Z ddc:004 open_access

An Empirical Evaluation of k-Means Coresets Schwiegelshohn, Chris Sheikh-Omar, Omar Ali coresets k-means coresets evaluation benchmark Coresets are among the most popular paradigms for summarizing data. In particular, there exist many high performance coresets for clustering problems such as k-means in both theory and practice. Curiously, there exists no work on comparing the quality of available k-means coresets. In this paper we perform such an evaluation. There currently is no algorithm known to measure the distortion of a candidate coreset. We provide some evidence as to why this might be computationally difficult. To complement this, we propose a benchmark for which we argue that computing coresets is challenging and which also allows us an easy (heuristic) evaluation of coresets. Using this benchmark and real-world data sets, we conduct an exhaustive evaluation of the most commonly used coreset algorithms from theory and practice. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chris Schwiegelshohn and Omar Ali Sheikh-Omar 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.84 urn:nbn:de:0030-drops-170225 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.84 eng https://creativecommons.org/licenses/by/4.0/legalcode