RACK: RApid clustering using K-means algorithm

Vikas K. Garg, M. N. Murty

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

Abstract

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
Pages621-626
Number of pages6
DOIs
Publication statusPublished - 2009
MoE publication typeA4 Article in a conference publication
EventIEEE International Conference on Automation Science and Engineering - Bangalore, India
Duration: 22 Aug 200925 Aug 2009

Conference

ConferenceIEEE International Conference on Automation Science and Engineering
Abbreviated titleCASE
CountryIndia
CityBangalore
Period22/08/200925/08/2009

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

Cite this