Experimental evaluation of fully dynamic k-means via coresets

Henzinger MH, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.


Conference Paper | Published | English
Abstract
For a set of points in Rd, the Euclidean k-means problems consists of finding k centers such that the sum of distances squared from each data point to its closest center is minimized. Coresets are one the main tools developed recently to solve this problem in a big data context. They allow to compress the initial dataset while preserving its structure: running any algorithm on the coreset provides a guarantee almost equivalent to running it on the full data. In this work, we study coresets in a fully-dynamic setting: points are added and deleted with the goal to efficiently maintain a coreset with which a k-means solution can be computed. Based on an algorithm from Henzinger and Kale [ESA'20], we present an efficient and practical implementation of a fully dynamic coreset algorithm, that improves the running time by up to a factor of 20 compared to our non-optimized implementation of the algorithm by Henzinger and Kale, without sacrificing more than 7% on the quality of the k-means solution.
Publishing Year
Date Published
2024-01-04
Proceedings Title
2024 Proceedings of the Symposium on Algorithm Engineering and Experiments
Acknowledgement
This project has received funding from the Euro-pean Research Council (ERC) under the EuropeanUnion’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The De-sign of Modern Fully Dynamic Data Structures (Mo-DynStruct)” and the Austrian Science Fund (FWF)project Z 422-N, project “Static and Dynamic Hierar-chical Graph Decompositions”, I 5982-N, and project“Fast Algorithms for a Reactive Network Layer (Re-actNet)”, P 33775-N, with additional funding from thenetidee SCIENCE Stiftung, 2020–2024.D. Sauplic has received funding from the Euro-pean Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreementNo 101034413.
Page
220-233
Conference
ALENEX: Workshop on Algorithm Engineering and Experiments
Conference Location
Alexandria, VA, United States
Conference Date
2024-01-07 – 2024-01-08
IST-REx-ID

Cite this

Henzinger MH, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means via coresets. In: 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. Society for Industrial & Applied Mathematics; 2024:220-233. doi:10.1137/1.9781611977929.17
Henzinger, M. H., Saulpic, D., & Sidl, L. (2024). Experimental evaluation of fully dynamic k-means via coresets. In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (pp. 220–233). Alexandria, VA, United States: Society for Industrial & Applied Mathematics. https://doi.org/10.1137/1.9781611977929.17
Henzinger, Monika H, David Saulpic, and Leonhard Sidl. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, 220–33. Society for Industrial & Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977929.17.
M. H. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic k-means via coresets,” in 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2024, pp. 220–233.
Henzinger MH, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.
Henzinger, Monika H., et al. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial & Applied Mathematics, 2024, pp. 220–33, doi:10.1137/1.9781611977929.17.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2310.18034

Search this title in

Google Scholar