RACK: RApid clustering using K-means algorithm

Vikas K. Garg, M. N. Murty

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review


The k-means algorithm is an extremely popular technique for clustering data. One of the major limitations of the k-means is that the time to cluster a given dataset D is linear in the number of clusters, k. In this paper, we employ height balanced trees to address this issue. Specifically, we make two major contributions, (a) we propose an algorithm, RACK (acronym for RApid Clustering using k-means), which takes time favorably comparable with the fastest known existing techniques, and (b) we prove an expected bound on the quality of clustering achieved using RACK. Our experimental results on large datasets strongly suggest that RACK is competitive with the k-means algorithm in terms of quality of clustering, while taking significantly less time.

Original languageEnglish
Title of host publication2009 IEEE International Conference on Automation Science and Engineering, CASE 2009
Number of pages6
Publication statusPublished - 2009
MoE publication typeA4 Conference publication
EventIEEE International Conference on Automation Science and Engineering - Bangalore, India
Duration: 22 Aug 200925 Aug 2009


ConferenceIEEE International Conference on Automation Science and Engineering
Abbreviated titleCASE


Dive into the research topics of 'RACK: RApid clustering using K-means algorithm'. Together they form a unique fingerprint.

Cite this