GPU Acceleration of Iterative Clustering

Abstract

Iterative clustering algorithms based on Lloyds algorithm (often referred to as the k-means algorithm) have been used in a wide variety of areas, including graphics, computer vision, signal processing, compression, and computational geometry. We describe a method for accelerating many variants of iterative clustering by using programmable graphics hardware to perform the most computationally expensive portion of the work. In particular, we demonstrate significant speedups for k-means clustering (essential in vector quantization) and clustered principal component analysis. An additional contribution is a new hierarchical algorithm for k-means which performs less work than the brute-force algorithm, but which offers significantly more SIMD parallelism than the straightforward hierarchical approach.