Approximate Nearest Centroid Embedding for Kernel k-Means

This paper proposes an efficient embedding method for scaling kernel k-means on cloud infrastructures. The embedding method allows for approximating the com-putation of the nearest centroid to each data instance and, accordingly, it elim-inates the quadratic space and time complexities of the cluster assignment step in the kernel k-means algorithm. We show that the proposed embedding method is effective under memory and computing power constraints, and that it achieves better clustering performance compared to other approximations of the kernel k-means algorithm.