# Heterogeneous Distributed Big Data Clustering on Sparse Grids
## 1 Introduction  
In data mining, cluster analysis partitions a dataset according to a given measure of similarity. The partitions obtained as a result of the clustering process are called clusters. The clustering of big datasets poses additional challenges as not all clustering algorithms scale well in the size of the dataset. Furthermore, mapping clustering approaches to modern hardware platforms such as graphics processing units (GPUs) requires new parallel approaches. And for the use on supercomputers or in the cloud, algorithms need to be designed for distributed computing. There is a wide range of algorithms that perform clustering. The classic \(k\)-means algorithm iteratively improves an initial guess of cluster centers [1]. Efficient variants of the \(k\)-means algorithm have been proposed, e.g., by using domain partitioning through \(k\)-\(d\)-trees [2] or by a more careful selection of the initial cluster centers [3]. As a major disadvantage, \(k\)-means requires the number of clusters to be known in advance, which is not always possible. Moreover, in contrast to many alternatives, \(k\)-means cannot detect clusters with non-convex shape. DBSCAN probably is the most widely used density-based clustering approach [4]. In its basic form, it constructs a cluster based on the number of data points in an \(\epsilon\)-sphere around each data point. If spheres overlap and have enough data points in them, the data points are part of the same cluster. For \(m\) data points, the complexity of DBSCAN was stated as \(\mathcal{O}(m\log m)\) in the original paper [4]. However, more recent work shows that the actual complexity has a lower bound of \(\Omega(m^{4/3})\)[5; 6]. DENCLUE is another example for clustering based on density estimation. It uses a kernel density estimation algorithm [7]. Spectral clustering methods cluster datasets by solving a mincut problem on a weighted neighborhood graph [8]. There are many more approaches to clustering, e.g., using neural networks [9], described in the literature [1; 10]. Some clustering algorithms support GPUs for higher performance. [PERSON] and [PERSON] presented a distributed and GPU-accelerated \(k\)-means implementation in 2006, before modern GPGPU frameworks like CUDA and OpenCL were available [11]. Since then, further GPU-enabled \(k\)-means algorithms have been developed [12; 13; 14; 15]. Fewer published results are available for density-based GPU-accelerated clustering. CUDA-DClust is a GPU-accelerated variant of DBSCAN that uses an indexing approach to reduce distance calculations [16]. [PERSON] et al. developed a GPU-accelerated variant of DBSCAN called G-DBSCAN employing an algorithm with quadratic complexity in the dataset size [17]. While many clustering algorithms have been proposed, not many have been shown to work in big data scenarios. \(k\)-means++ is a map-reduce variant of the \(k\)-mean algorithm that has been used to cluster a 4.8 million data points dataset on a Hadoop cluster with 1968 nodes [18]. MR-DBSCAN is a DBSCAN variant that could cluster a 2-D dataset with up to 1.9 billion data points and is implemented with a map-reduce approach as well [19]. The published results of MR-DBSCAN demonstrate excellent performance. However, it uses a grid discretization that makes assumptions on the distribution of the dataset throughout the domain. Furthermore, it is unclear how the algorithm will scale to higher dimensions, as the grid discretization is fully affected by the issue of dimensionality [20]. RP-DBSCAN implements a similar approach compared to MR-DBSCAN, but uses a more advanced partitioning scheme [5]. RP-DBSCAN was able cluster a 13-D dataset with 4.4 billion data points. In this work, we introduce a new distributed and performance-portable variant of the sparse grid clustering algorithm. This approach builds upon prior work which presented the basic theory and compared our approach to other clustering strategies [21]. The unique building block of our approach is the sparse grid density estimation algorithm.