Abstract
We exploit the parallel architecture of the Graphics Processing Unit (GPU) used in desktops to efficiently implement the traditional K-means algorithm. Our approach in clustering avoids the need for data and cluster information transfer between the GPU and CPU in between the iterations. In this paper we present the novelties in our approach and techniques employed to represent data, compute distances, centroids and identify the cluster elements using the GPU. We measure performance using the metric: computational time per iteration. Our implementation of k-means clustering on an Nvidia 5900 graphics processor is 4 to 12 times faster than the CPU and 7 to 22 times faster on the Nvidia 8500 graphics processor for various data sizes. We also achieved 12 to 64 times speed gain on the 5900 and 20 to 140 times speed gains on the 8500 graphics processor in computational time per iteration for evaluations with various cluster sizes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fluck, O., Aharon, S., Cremers, D., Rousson, M.: GPU histogram computation. In: International Conference on Computer Graphics and Interactive Techniques, ACM SIGGRAPH (2006)
Cao, F., Tung, A.K.H., Zhou, A.: Scalable Clustering Using Graphics Processors. In: Yu, J.X., Kitsuregawa, M., Leong, H.-V. (eds.) WAIM 2006. LNCS, vol. 4016. Springer, Heidelberg (2006)
Hall, J.D., Hart, J.C.: GPU Acceleration of Iterative Clustering. In: The ACM Workshop on GPC on GPU & SIGRAPH (2004)
Richard, W.S., Lipchak, B.: OpenGL SuperBible. Sams Publishing (2005)
Göddeke, D.: Basic Math Tutorial. Retrieved from GPGPU (2007), http://www.mathematik.uni-dortmund.de/~goeddeke/gpgpu/tutorial.html
Göddeke, D.: Reduction Tutorial. Retrieved from GPGPU (2007), http://www.mathematik.uni-dortmund.de/~goeddeke/gpgpu/tutorial2.html
NVIDIA. GPU Gems 2. ADDISON-WESLEY (2006)
Zhang, Q., Zhang, Y.: Hierarchical clustering of gene expression profiles with graphics hardware acceleration. Pattern Recognition Letters 27, 676–681 (2006)
Owens, J.D., Luebke, D., Govindaraju, N., Harris, M., Krüger, J., Lefohn, A.E., Purcell, T.J.: A Survey of General-Purpose Computation on Graphics Hardware. In: Eurographics (2006)
Owens, J.D.: Streaming Architectures and Technology Trends. In: GPU Gems2, ch. 29, pp. 457–470 (2004)
Rost, R.J.: OpenGL® Shading Language, 2nd edn. Addison Wesley Professional, Reading (2006)
Intelligent Data Storage for Data-Intensive Analytical Systems. Real Data Set covtype Downloaded from D∙Star (2007), http://uisacad2.uis.edu/dstar/data/clusteringdata.html
Takizawa, H., Kobayashi, H.: Hierarchical parallel processing of large scale data clustering on a PC cluster with GPU co-processing. J. Supercomputing 36, 219–234 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shalom, S.A.A., Dash, M., Tue, M. (2008). Efficient K-Means Clustering Using Accelerated Graphics Processors. In: Song, IY., Eder, J., Nguyen, T.M. (eds) Data Warehousing and Knowledge Discovery. DaWaK 2008. Lecture Notes in Computer Science, vol 5182. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85836-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-85836-2_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85835-5
Online ISBN: 978-3-540-85836-2
eBook Packages: Computer ScienceComputer Science (R0)