Speeding up k-Means algorithm by GPUs

You Li, Kaiyong Zhao, Xiaowen CHU*, Jiming LIU

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

45 Citations (Scopus)

Abstract

Cluster analysis plays a critical role in a wide variety of applications; but it is now facing the computational challenge due to the continuously increasing data volume. Parallel computing is one of the most promising solutions to overcoming the computational challenge. In this paper, we target at parallelizing k-Means, which is one of the most popular clustering algorithms, by using the widely available Graphics Processing Units (GPUs). Different from existing GPU-based k-Means algorithms, we observe that data dimensionality is an important factor that should be taken into consideration when parallelizing k-Means on GPUs. In particular, we use two different strategies for low-dimensional data sets and high-dimensional data sets respectively, in order to make the best use of GPU computing horsepower. For low-dimensional data sets, we design an algorithm that exploits GPU on-chip registers to significantly decrease the data access latency. For high-dimensional data sets, we design another novel algorithm that simulates matrix multiplication and exploits GPU on-chip shared memory to achieve high compute-to-memory-access ratio. Our experimental results show that our GPU-based k-Means algorithms are three to eight times faster than the best reported GPU-based algorithms.

Original languageEnglish
Pages (from-to)216-229
Number of pages14
JournalJournal of Computer and System Sciences
Volume79
Issue number2
DOIs
Publication statusPublished - Mar 2013

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Clustering
  • CUDA
  • GPU computing
  • k-Means

Fingerprint

Dive into the research topics of 'Speeding up k-Means algorithm by GPUs'. Together they form a unique fingerprint.

Cite this