arbiter
JournalsPricingAccount

FastKPP: An exact accelerated k -means + + algorithm

Guillem Rodríguez Corominas et al.

Software Impacts2026https://doi.org/10.1016/j.simpa.2026.100830article
AJG 1
Weight
0.50

What the paper says

In this paper, we present FastKpp , a C++ implementation of an exact accelerated k -means + + algorithm using two geometry-aware filters: one based on the Triangle Inequality (TIE) and another based on point norms. Both provably preserve the original D 2 sampling distribution while avoiding redundant distance computations. The library provides a header-only API, a command-line tool, and a fully reproducible capsule. Experiments show substantial reductions in distance computations and speedups that increase with k (with typical median between 2 and 8). Furthermore, FastKpp outperforms other state-of-the-art exact acceleration techniques. Results are reproducible via the public GitHub repository and Code Ocean capsule. • Exact k-means++ acceleration with TIE and norm filters preserving D 2 sampling. • Large speedups that increase with k by reducing the number of distance evaluations. • The TIE version excels in low dimensions, while the TIE+Norm version leads in high-dimensional data with high norm variance. • Header-only C++ library with drop-in API and CLI. • Tight per-point lower bounds computed during seeding for later k-means accelerations.

Open paper page →

Cite this paper

https://doi.org/https://doi.org/10.1016/j.simpa.2026.100830

Or copy a formatted citation

@article{guillem2026,
  title        = {{FastKPP: An exact accelerated k -means + + algorithm}},
  author       = {Guillem Rodríguez Corominas et al.},
  journal      = {Software Impacts},
  year         = {2026},
  doi          = {https://doi.org/https://doi.org/10.1016/j.simpa.2026.100830},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

FastKPP: An exact accelerated k -means + + algorithm

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.