A summary of A survey on parallel clustering algorithms for Big Data

Vol.:(0123456789)

Artificial Intelligence Review https://doi.org/10.1007/s10462-020-09918-2

1 3

A survey on parallel clustering algorithms for Big Data

Zineb Dafir1  · Yasmine Lamari1 · Said Chah Slaoui1

© Springer Nature B.V. 2020

Abstract Data clustering is one of the most studied data mining tasks. It aims, through various meth- ods, to discover previously unknown groups within the data sets. In the past years, con- siderable progress has been made in this field leading to the development of innovative and promising clustering algorithms. These traditional clustering algorithms present some serious issues in connection with the speed-up, the throughput, and the scalability. Thus, they can no longer be directly used in the context of Big Data, where data are mainly char- acterized by their volume, velocity, and variety. In order to overcome their limitations, the research today is heading to the parallel computing concept by giving rise to the so-called parallel clustering algorithms. This paper presents an overview of the latest parallel clus- tering algorithms categorized according to the computing platforms used to handle the Big Data, namely, the horizontal and vertical scaling platforms. The former category includes peer-to-peer networks, MapReduce, and Spark platforms, while the latter category includes Multi-core processors, Graphics Processing Unit, and Field Programmable Gate Arrays platforms. In addition, it includes a comparison of the performance of the reviewed algo- rithms based on some common criteria of clustering validation in the Big Data context. Therefore, it provides the reader with an overall vision of the current parallel clustering techniques.

Keywords Algorithms · Big Data · Clustering · Data mining · DBSCAN · FPGA · GPU · k-means · MapReduce · MPI · Multi-cores CPU · Spark

1 Introduction

With the advent of the Big Data phenomenon, the data analysis techniques are currently being modernized in order to address the emerging challenges. Data clustering is no excep- tion to this trend. This long-established data mining technique is used to partition a set

* Zineb Dafir [email protected]

Yasmine Lamari [email protected]

Said Chah Slaoui [email protected]

1 Faculty of Science of Rabat, Mohammed V University, Rabat, Morocco

Z. Dafir et al.

1 3

of data instances into homogeneous subsets, such that each subset is formed by similar instances, and at the same time dissimilar to instances belonging to other subsets (Han et  al. 2012). The primary objective is to discover previously unknown groups, which is a sought-after result in several problems in everyday life. This can be achieved through dif- ferent categories of clustering methods such as hierarchical methods, partitioning methods, density-based methods, grid-based methods, or other clustering techniques (Fahad et  al. 2014).

1.1 Challenges

Most traditional clustering algorithms are specialized and operate under specific conditions to solve a particular type of problem. Besides, they are outdated and impractical in the context of the Big Data due to their computational costs and their inability to handle het- erogeneous data. They also suffer from their dependence on prior knowledge, data order, and complex input parameters. In order to overcome these limitations, the research today is heading to the parallel computing concept by giving rise to the so-called parallel clustering algorithms. As the designation implies, this kind of algorithms can partition data sets into several chunks, and then for each chunk, execute activities simultaneously on one or on many processing devices. The intermediate clustering results are usually aggregated at the end to produce the final result. The concept of parallelism aims to improve the speed-up, the throughput, and the scalability of the clustering process so that it becomes effective to meet the challenges of Big Data.

These challenges arise primarily from the characteristics that define the Big Data, namely the volume, the velocity, and the variety of data, which stand for the 3V’s defini- tion proposed by the Gartner company in Laney (2001). The first dimension refers to the quantity of generated and stored data. Recently, the volume of data ranges from petabytes toward zettabytes in a continued increase. Then, the second dimension represents the fre- quency at which the data is coming and updated because the data is constantly in motion. The third dimension to be also considered is the variety of data, since data is collected from multiple sources and in different forms. These dimensions describe the Big Data phe- nomenon, and they serve also as criteria for evaluating algorithms that attempt to solve the Big Data issues such as clustering algorithms.

1.2 Scope of the article

This paper presents an overview of the latest parallel clustering algorithms categorized according to the computing platforms used to handle the Big Data. Indeed, at some point, we need to know what has been accomplished and what remains to be done regarding the clustering of Big Data. Accordingly, this paper aims to provide the reader with an overall vision of the parallel methods of clustering Big Data that have been developed recently as well as the current trend of the research in such relevant field. In this respect, we opted for a recent classification of the different platforms for the Big Data analytic which is proposed in Singh and Reddy (2014). According to this classification, two categories of platforms of Big Data can be distinguished: the horizontal scaling platforms and the vertical scal- ing platforms. The first category gathers systems that distribute the workload across many servers or commodity machines. And so it includes peer-to-peer networks, MapReduce, and Spark platforms. While the second category brings together systems that work on a single server and allows adding additional resources, such as processors, memory, and fast

A survey on parallel clustering algorithms for Big Data

1 3

hardware. This category includes High Performance Computing Clusters (HPC), Multi- core processors, Graphics Processing Unit (GPU), and Field Programmable Gate Arrays (FPGA) platforms. Figure 1 illustrates the classification of different Big Data platforms.

1.3 Contributions

This section explores the fundamental contributions of this paper as follows:

1. Presents a technical overview of different Big Data platforms. 2. Surveys the new parallel clustering algorithms and their categorization according to the

platforms adopted to ensure their parallelization. 3. Introduces a comparison of the algorithms studied in terms of clustering validation

criteria and Big Data characteristics.

1.4 Organization

The remainder of this survey is organized as follows: Sect. 2 reviews the most popular plat- forms of Big Data. Section 3 exposes the most recent parallel clustering methods classified based on the used platform. Section 4 compares the studied parallel clustering algorithms.

Fig. 1 Classification of Big data platforms

Z. Dafir et al.

1 3

Finally, Sect.  5 summarizes the main observations of this survey and the corresponding recommendations.

2 Overview of the different platforms of Big Data

This section presents a brief overview of the most popular platforms of Big Data. First, the horizontal scaling platforms are presented, including MapReduce, Spark, and Peer-to-peer networks. Then, the vertical scaling platforms are presented, which comprise Graphics Processing Unit, Multi-core CPU, and Field Programmable Gate Arrays. These platforms have been the basis for several designs and clustering algorithms of which some relevant works are examined in this paper.

2.1 MapReduce

MapReduce is a popular parallel programming model, which was first introduced by Google in Dean and Ghemawat (2004). It was designed to read, process, and write a huge amount of data. This programming model consists of two main functions: the Map and the Reduce functions. The Map function takes as input a logical record (also called a chunk of data) and produces a set of intermediate key/value pairs. Once the Map phase is completed, the Reduce phase starts processing the intermediate key/value pairs produced in the previ- ous phase. Indeed, the Reduce function takes as input the set of intermediate key/value pairs that share the same key, and then, merges together all values assigned to the input key in order to produce the set of values associated with the corresponding key. There are two other optional functions used to refine the execution of the programs: the Partitioner and the Combiner functions. The Partitioner function splits the intermediate keys according to the number of Reduce tasks or the number of output files which is specified by the devel- oper. The Combiner function aims to summarize intermediate results produced by each Map task in order to avoid potential repetitions, thus optimizing the transfer of data to the Reduce task over the network. All these functions are programmable by the developer. Fig- ure  2 describes the operational flowchart of the MapReduce programming model (Dean and Ghemawat 2004).

Fig. 2 Flowchart of MapReduce model

A survey on parallel clustering algorithms for Big Data

1 3

2.2 Spark

Apache Spark is a big data processing framework designed for data-intensive applica- tions and executed on commodity clusters (Zaharia et  al. 2010). Unlike MapReduce, Spark framework supports iterative jobs and allows running queries on big datasets by loading only the useful dataset into memory. In this way, the execution time is reduced considerably.

Spark introduces three fundamental aspects: resilient distributed datasets (RDDs), par- allel operations, and shared variables. RDD is a collection of objects shared by a set of machines that can be recovered in case of loss; it can be also stored in memory to reuse it in multiple parallel MapReduce jobs. The second aspect is the parallel operations which can be performed on RDDs. It includes the Reduce, Collect and Foreach operations. The last aspect consists of broadcast variables and accumulators.

Spark is flexible, easy to use and does not need any abstraction to program. It pro- cesses the data in real-time using the Spark Streaming module and caches partial results in memory using distributed workers. Moreover, Spark is efficient and exceeds the Hadoop MapReduce framework by 10× in interactive machine learning workloads while preserving the fault tolerance and scalability of MapReduce. However, Spark shows some limitations, such as the fact that it requires large resources, and it is also expensive in terms of memory. Figure 3 depicts the operational flowchart of the Spark model (Zaharia et al. 2010).

2.3 Peer‑to‑peer networks

Peer-to-peer (P2P) networking represents a distributed architecture that divides tasks among peers. The definition of P2P networking includes any type of network architec- ture which does not need a server to control the transfer of information between contrib- utors, and which makes a part of their resources accessible by other contributors in the same network (Milojicic et al. 2002). Hence, P2P systems allow valuable externalities, lower cost of ownership and sharing, and finally anonymity. The most used scheme in this platform is the Message Passing Interface (MPI). The fundamental idea behind the standard MPI is to provide the necessary abstractions in order to ensure the communica- tion between peers. It is also characterized by its ability to keep processes alive during

Fig. 3 Flowchart of Apache Spark model

Z. Dafir et al.

1 3

the running of the system, which means that there is no need to read the data several times from the disk. This quality makes the MPI suitable for iterative jobs.

The Architecture of P2P network has the ability to add nodes dynamically and thus to scale up efficiently to a larger size that may be needed to process applications with a huge amount of data, as shown in Fig. 4. This kind of platforms is known to be resistant to failures, which means that when a node experiences a local failure, it will have no impact on the remaining nodes. Another advantage lies in the fact that the capacity of a P2P system increases with the addition of new nodes. However, adding new nodes to the system can slow down the transfer of data to the connected users. P2P systems suffer also from security issues and require high bandwidth usage.

Fig. 4 A typical architecture of the peer-to-peer network

A survey on parallel clustering algorithms for Big Data

1 3

2.4 Graphics processing unit

A Graphics Processing Unit (GPU) is a single-chip processor which was initially dedicated for processing 2D and 3D calculations. As an input, it receives geometry primitives from the CPU in a 3D form. Then it transforms them from individual vertices into pixels, which are shaded and mapped onto the screen. In order to produce the final image, the processed pixels are combined to form an output destined to be visualized in a display device. These stages form the so-called graphics pipeline as shown in Fig.  5 (Owens et  al. 2008). The GPUs follow the single program multiple data (SPMD) as a programming model and the single instruction, multiple data (SIMD) as parallel architecture.

Today, modern GPUs are gaining increasing attention due to their massively parallel processing architecture that accelerates the performance of applications requiring high floating point calculations. Indeed, GPUs are not beneficial only for graphics applications; they are also used to perform non-specialized calculations giving rise to the general pur- pose graphics processing unit (GPGPU) computing. In order to take full advantage of the parallelism offered by GPUs, new parallel programming languages, such as CUDA (Nick- olls et al. 2008) and OpenCL (Stone et al. 2010), have emerged. These languages simplify and improve the performance of the linear algebra on the GPUs (Owens et al. 2008).

GPUs have demonstrated energy and cost efficiency for arithmetical intense and stream- ing-memory problems. However, their major drawback lies in the limited memory capac- ity, which often necessitates complex memory management.

2.5 Multi‑core CPU

A Multi-core platform is a processor that integrates multiple cores in a single chip. Gener- ally, there are three commonly recognized architectures of multi-core CPU (Akhter and Roberts 2006). The first architecture shares the on-chip cache between execution units, while the second architecture provides a dedicated cache for each execution core. The third architecture adopts a hybrid approach that subdivided the cache into two types of layers,

Fig. 5 A typical structure of graphics pipeline

Z. Dafir et al.

1 3

layers dedicated to a particular execution core and others shared by all execution cores. Figure 6 describes a typical architecture of multi-core platform.

In order to take advantage of the parallelism offered by the multi-core platforms, one has to consider the allocation of the work among all available processors (Gepner and Kowalik 2006). The multi-threading model is a common way that allows the parallel execution on a multi-core platform. This is achieved by dividing the work into separate execution units which can run on the different processors at the same time.

The multi-core platforms offer a high performance and low heat generation. They are useful for applications with high capacity of parallelism that can profit from all the avail- able cores, otherwise, the multi-core platforms won’t be a practical choice. This entails a substantial effort to parallelize an application as far as possible, which is not always feasible.

2.6 Field programmable gate arrays

A Field Programmable Gate Arrays (FPGA) is an integrated circuit device. It is composed of an array of programmable logic blocks, in addition to a hierarchy of reconfigurable inter- connects and I/O blocks (Brown et  al. 1992). Different architectures of logic blocks can be conceived in order to form a complex circuit. Such circuits contain several other sub- circuits and have more than one output. These blocks are interconnected via reconfigurable interconnects, which consists of wire segments and programmable switches. Like the logic blocks, the structure of programmable switches can be conceived in different ways. The configurations of all components of the FPGA are described using a hardware description language (HDL).

The main advantages of FPGAs lie in the reduced costs of prototypes they offer, in addition to their expandability and flexibility. In fact, the flexibility is regarded as both an advantage and a drawback since it makes the FPGAs larger, slower, and more power con- suming (Farooq et al. 2012).

The FPGAs are omnipresent in various applications and can figure out any computa- tional problem, especially the applications that require exploiting the parallelism available on FPGAs.

Fig. 6 A typical architecture of multi-core platform