GPU Acceleration of Iterative Clustering

Manuscript accompanying poster at GP^2: The ACM Workshop on General Purpose Computing on Graphics Processors, and SIGGRAPH 2004 poster, Aug. 2004

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.

gpucluster.pdf985.06 KB

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer