An Empirical Evaluation of $k$-Means Coresets
This work addresses a gap in summarizing data for clustering problems, but it is incremental as it focuses on evaluation rather than new methods.
The paper tackled the lack of empirical comparison for k-means coresets by proposing a benchmark to evaluate their quality, finding that computing coresets is challenging and providing evidence for computational difficulty.
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.