Speeding up k-means by approximating Euclidean distances via block vectors


Thomas Bottesch, Thomas Bühler, Markus Kächele ;
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2578-2586, 2016.


This paper introduces a new method to approximate Euclidean distances between points using block vectors in combination with the Hölder inequality. By defining lower bounds based on the proposed approximation, cluster algorithms can be considerably accelerated without loss of quality. In extensive experiments, we show a considerable reduction in terms of computational time in comparison to standard methods and the recently proposed Yinyang k-means. Additionally we show that the memory consumption of the presented clustering algorithm does not depend on the number of clusters, which makes the approach suitable for large scale problems.

Related Material