Heterogeneous Distributed Big Data Clustering on Sparse Grids
Open Access
- 7 March 2019
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 12 (3) , 60
Abstract
Clustering is an important task in data mining that has become more challenging due to the ever-increasing size of available datasets. To cope with these big data scenarios, a high-performance clustering approach is required. Sparse grid clustering is a density-based clustering method that uses a sparse grid density estimation as its central building block. The underlying density estimation approach enables the detection of clusters with non-convex shapes and without a predetermined number of clusters. In this work, we introduce a new distributed and performance-portable variant of the sparse grid clustering algorithm that is suited for big data settings. Our computed kernels were implemented in OpenCL to enable portability across a wide range of architectures. For distributed environments, we added a manager–worker scheme that was implemented using MPI. In experiments on two supercomputers, Piz Daint and Hazel Hen, with up to 100 million data points in a ten-dimensional dataset, we show the performance and scalability of our approach. The dataset with 100 million data points was clustered in 1198 using 128 nodes of Piz Daint. This translates to an overall performance of 352 . On the node-level, we provide results for two GPUs, Nvidia’s Tesla P100 and the AMD FirePro W8100, and one processor-based platform that uses Intel Xeon E5-2680v3 processors. In these experiments, we achieved between 43% and 66% of the peak performance across all computed kernels and devices, demonstrating the performance portability of our approach.
Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (EXC 310/2)
This publication has 25 references indexed in Scilit:
- MR-DBSCAN: a scalable MapReduce-based DBSCAN algorithm for heavily skewed dataFrontiers of Computer Science, 2013
- G-DBSCAN: A GPU Accelerated Algorithm for Density-based ClusteringProcedia Computer Science, 2013
- Emerging Architectures Enable to Boost Massively Parallel Data Mining Using Adaptive Sparse GridsInternational Journal of Parallel Programming, 2012
- Parallel data mining techniques on Graphics Processing Unit with Compute Unified Device Architecture (CUDA)The Journal of Supercomputing, 2011
- A tutorial on spectral clusteringStatistics and Computing, 2007
- Hierarchical parallel processing of large scale data clustering on a PC cluster with GPU co-processingThe Journal of Supercomputing, 2006
- Sparse gridsActa Numerica, 2004
- An efficient k-means clustering algorithm: analysis and implementationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Why so many clustering algorithmsACM SIGKDD Explorations Newsletter, 2002
- Classification of multicomponent analytical data of olive oils using different neural networksAnalytica Chimica Acta, 1994