RACK: RApid clustering using K-means algorithm

Vikas K. Garg; M. N. Murty

doi:10.1109/COASE.2009.5234127

RACK: RApid clustering using K-means algorithm

Vikas K. Garg, M. N. Murty

Not published at Aalto University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-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 language	English
Title of host publication	2009 IEEE International Conference on Automation Science and Engineering, CASE 2009
Pages	621-626
Number of pages	6
DOIs	https://doi.org/10.1109/COASE.2009.5234127
Publication status	Published - 2009
MoE publication type	A4 Article in a conference publication
Event	IEEE International Conference on Automation Science and Engineering - Bangalore, India Duration: 22 Aug 2009 → 25 Aug 2009

Conference

Conference	IEEE International Conference on Automation Science and Engineering
Abbreviated title	CASE
Country/Territory	India
City	Bangalore
Period	22/08/2009 → 25/08/2009

Access to Document

10.1109/COASE.2009.5234127

OpenUrl availability

Full text

Cite this

@inproceedings{083cf41a8d0748a19dead95ad9c0fa8a,

title = "RACK: RApid clustering using K-means algorithm",

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.",

author = "Garg, {Vikas K.} and Murty, {M. N.}",

year = "2009",

doi = "10.1109/COASE.2009.5234127",

language = "English",

isbn = "9781424445783",

pages = "621--626",

booktitle = "2009 IEEE International Conference on Automation Science and Engineering, CASE 2009",

note = "IEEE International Conference on Automation Science and Engineering, CASE ; Conference date: 22-08-2009 Through 25-08-2009",

}

TY - GEN

T1 - RACK

T2 - IEEE International Conference on Automation Science and Engineering

AU - Garg, Vikas K.

AU - Murty, M. N.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70449111629&partnerID=8YFLogxK

U2 - 10.1109/COASE.2009.5234127

DO - 10.1109/COASE.2009.5234127

M3 - Conference contribution

AN - SCOPUS:70449111629

SN - 9781424445783

SP - 621

EP - 626

BT - 2009 IEEE International Conference on Automation Science and Engineering, CASE 2009

Y2 - 22 August 2009 through 25 August 2009

ER -

RACK: RApid clustering using K-means algorithm

Abstract

Conference

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this