Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing

Ryan McConville, Xin Cao, Weiru Liu, Paul Miller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)
396 Downloads (Pure)


Most traditional data mining algorithms struggle to cope with the sheer scale of data efficiently. In this paper, we propose a general framework to accelerate existing clustering algorithms to cluster large-scale datasets which contain large numbers of attributes, items, and clusters. Our framework makes use of locality sensitive hashing (LSH) to significantly reduce the cluster search space. We also theoretically prove that our framework has a guaranteed error bound in terms of the clustering quality. This framework can be applied to a set of centroid-based clustering algorithms that assign an object to the most similar cluster, and we adopt the popular K-Modes categorical clustering algorithm to present how the framework can be applied. We validated our framework with five synthetic datasets and a real world Yahoo! Answers dataset. The experimental results demonstrate that our framework is able to speed up the existing clustering algorithm between factors of 2 and 6, while maintaining comparable cluster purity.
Original languageEnglish
Title of host publicationProceedings of the 2016 IEEE 32nd International Conference on Data Engineering (ICDE)
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)978-1-5090-2020-1
Publication statusPublished - 01 May 2016
Event32nd IEEE International Conference on Data Engineering - Finland, Helsinki, Finland
Duration: 16 May 201620 May 2016


Conference32nd IEEE International Conference on Data Engineering


Dive into the research topics of 'Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing'. Together they form a unique fingerprint.

Cite this