logo Idiap Research Institute        
 [BibTeX] [Marc21]
Fast K-Means with Accurate Bounds
Type of publication: Idiap-RR
Citation: Newling_Idiap-RR-17-2016
Number: Idiap-RR-17-2016
Year: 2016
Month: 6
Institution: Idiap
Abstract: We propose a novel accelerated exact $k$-means algorithm, which outperforms the current state-of-the-art low-dimensional algorithm in 18 of 22 experiments, running up to 3$\times$ faster. We also propose a general improvement of existing state-of-the-art accelerated exact $k$-means algorithms through better estimates of the distance bounds used to reduce the number of distance calculations, obtaining speedups in 36 of 44 experiments, of up to 1.8$\times$. We have conducted experiments with our own implementations of existing methods to ensure homogeneous evaluation of performance, and we show that our implementations perform as well or better than existing available implementations. Finally, we propose simplified variants of standard approaches and show that they are faster than their fully-fledged counterparts in 59 of 62 experiments.
Keywords: accelerated exact k-means, Annulus, clustering, Elkan, exact k-means, Exponion, Hamerly, K-means, Yinyany
Projects Idiap
Authors Newling, James
Fleuret, Francois
Added by: [ADM]
Total mark: 0
  • Newling_Idiap-RR-17-2016.pdf (MD5: ef5d55669c5dc522a57db9db2236f4c8)
       (ICML camera ready (+supp))