Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing

Ryan McConville; Xin Cao; Weiru Liu; Paul Miller

doi:10.1109/ICDE.2016.7498278

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 proceeding › Conference Contribution (Conference Proceeding)

5 Citations (Scopus)

318 Downloads (Pure)

Abstract

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 algorithms to cluster large-scale datasets which contain large numbers of attributes, items, and clusters. Our framework makes use of locality sensitive hashing 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 language	English
Title of host publication	2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016)
Subtitle of host publication	Proceedings of a meeting held 16-20 May 2016, Helsinki, Finland
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	649-660
Number of pages	12
ISBN (Electronic)	9781509020201
ISBN (Print)	9781509020218
DOIs	https://doi.org/10.1109/ICDE.2016.7498278
Publication status	Published - Aug 2016
Event	32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland Duration: 16 May 2016 → 20 May 2016

Conference

Conference	32nd IEEE International Conference on Data Engineering, ICDE 2016
Country/Territory	Finland
City	Helsinki
Period	16/05/16 → 20/05/16

Research Groups and Themes

Jean Golding

Keywords

Clustering algorithms
Algorithm design and analysis
file organisation
pattern clustering
large scale centroid-based clustering
locality sensitive hashing
large-scale datasets clustering
cluster search space reduction
K-modes categorical clustering algorithm
cluster purity

Access to Document

10.1109/ICDE.2016.7498278

Full-text PDF (accepted author manuscript)
This is the author accepted manuscript (AAM). The final published version (version of record) is available online via IEEE at http://ieeexplore.ieee.org/document/7498278/. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 587 KB

Handle.net

Persistent link

Cite this

McConville, R., Cao, X., Liu, W., & Miller, P. (2016). Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016): Proceedings of a meeting held 16-20 May 2016, Helsinki, Finland (pp. 649-660). Article 7498278 Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ICDE.2016.7498278

@inproceedings{353be5539f93412596a912d5eef5c89a,

title = "Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing",

abstract = "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 algorithms to cluster large-scale datasets which contain large numbers of attributes, items, and clusters. Our framework makes use of locality sensitive hashing 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.",

keywords = "Clustering algorithms, Algorithm design and analysis, file organisation, pattern clustering, large scale centroid-based clustering, locality sensitive hashing, large-scale datasets clustering, cluster search space reduction, K-modes categorical clustering algorithm, cluster purity",

author = "Ryan McConville and Xin Cao and Weiru Liu and Paul Miller",

year = "2016",

month = aug,

doi = "10.1109/ICDE.2016.7498278",

language = "English",

isbn = "9781509020218",

pages = "649--660",

booktitle = "2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "32nd IEEE International Conference on Data Engineering, ICDE 2016 ; Conference date: 16-05-2016 Through 20-05-2016",

}

McConville, R, Cao, X, Liu, W & Miller, P 2016, Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing. in 2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016): Proceedings of a meeting held 16-20 May 2016, Helsinki, Finland., 7498278, Institute of Electrical and Electronics Engineers (IEEE), pp. 649-660, 32nd IEEE International Conference on Data Engineering, ICDE 2016, Helsinki, Finland, 16/05/16. https://doi.org/10.1109/ICDE.2016.7498278

Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing. / McConville, Ryan; Cao, Xin; Liu, Weiru et al.
2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016): Proceedings of a meeting held 16-20 May 2016, Helsinki, Finland. Institute of Electrical and Electronics Engineers (IEEE), 2016. p. 649-660 7498278.

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing

AU - McConville, Ryan

AU - Cao, Xin

AU - Liu, Weiru

AU - Miller, Paul

PY - 2016/8

Y1 - 2016/8

N2 - 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 algorithms to cluster large-scale datasets which contain large numbers of attributes, items, and clusters. Our framework makes use of locality sensitive hashing 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.

AB - 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 algorithms to cluster large-scale datasets which contain large numbers of attributes, items, and clusters. Our framework makes use of locality sensitive hashing 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.

KW - Clustering algorithms

KW - Algorithm design and analysis

KW - file organisation

KW - pattern clustering

KW - large scale centroid-based clustering

KW - locality sensitive hashing

KW - large-scale datasets clustering

KW - cluster search space reduction

KW - K-modes categorical clustering algorithm

KW - cluster purity

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

U2 - 10.1109/ICDE.2016.7498278

DO - 10.1109/ICDE.2016.7498278

M3 - Conference Contribution (Conference Proceeding)

SN - 9781509020218

SP - 649

EP - 660

BT - 2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016)

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 32nd IEEE International Conference on Data Engineering, ICDE 2016

Y2 - 16 May 2016 through 20 May 2016

ER -

McConville R, Cao X, Liu W, Miller P. Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016): Proceedings of a meeting held 16-20 May 2016, Helsinki, Finland. Institute of Electrical and Electronics Engineers (IEEE). 2016. p. 649-660. 7498278 Epub 2016 Jun 23. doi: 10.1109/ICDE.2016.7498278

Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing

Abstract

Conference

Research Groups and Themes

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Professor Weiru Liu

Dr Ryan McConville

Cite this

Accelerating Large Scale Centroid-based Clustering with Locality Sensitive Hashing

Abstract

Conference

Research Groups and Themes

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Profiles

Professor Weiru Liu

Dr Ryan McConville

Cite this