GPU Acceleration of Iterative Clustering
University of Illinois at Urbana-Champaign
The ACM Workshop on General Purpose Computing on Graphics Processors, 2004
@conference{hall2004gpu,
title={GPU acceleration of iterative clustering},
author={Hall, J.D. and Hart, J.C.},
booktitle={Manuscript accompanying poster at GP2: The ACM Workshop on General Purpose Computing on Graphics Processors, and SIGGRAPH},
year={2004},
organization={Citeseer}
}
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. 1.
December 21, 2010 by hgpu
