REMOLD: An efficient model-based clustering algorithm for large datasets with spark

Mingfei Liang, Qingyong Li, Yangli Ao Geng, Jianzhu Wang, Zhi Wei

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

4 Scopus citations

Abstract

Density-based clustering algorithms have the distinctive advantage of discovering arbitrarily shaped clusters, but they usually require a procedure to compute the distance between every pair of data points, and this procedure is prohibitive for large datasets since it has quadratic computation complexity. In this paper, we propose a new distributed clustering algorithm, named REstore MOdel with Local Density estimation (REMOLD). Firstly, REMODL applies a balanced partitioning method to evenly divide an large dataset based on Local Sensitive Hashing (LSH). Then, it locally clusters each partition of the dataset, and uses a Gaussian model to represent each local cluster based on the observation that the density distribution of each local cluster shares similar shape with Gaussian distribution. Finally, these models are aggregated on a server where REMOLD restores global clusters based on these local Gaussian models. More specifically, model connection, which measures the density connectivity between two models, are defined to merge local models with an optimized procedure. In this aggregation, REMOLD requires low cost of network transmission for local Gaussian models, since the number of Gaussian models is often less than that of core objects for each partition. We evaluate REMOLD on three synthetic datasets and three real-world datasets on Spark, and the experiment results demonstrate that REMOLD is efficient and effective to find out clusters with complex shapes and it outperforms the established methods.

Original languageEnglish (US)
Title of host publicationProceedings - 2017 IEEE 23rd International Conference on Parallel and Distributed Systems, ICPADS 2017
PublisherIEEE Computer Society
Pages376-383
Number of pages8
ISBN (Electronic)9781538621295
DOIs
StatePublished - May 29 2018
Event23rd IEEE International Conference on Parallel and Distributed Systems, ICPADS 2017 - Shenzhen, China
Duration: Dec 15 2017Dec 17 2017

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume2017-December
ISSN (Print)1521-9097

Other

Other23rd IEEE International Conference on Parallel and Distributed Systems, ICPADS 2017
Country/TerritoryChina
CityShenzhen
Period12/15/1712/17/17

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Keywords

  • Density estimation
  • Density-based clustering
  • Distributed clustering
  • Gaussian model
  • Spark

Fingerprint

Dive into the research topics of 'REMOLD: An efficient model-based clustering algorithm for large datasets with spark'. Together they form a unique fingerprint.

Cite this