# Optimization Algorithms for Scalable Stream Batch Clustering with k Estimation
## 2 Related Work
F-EAC has already been used to cluster scalable batch data sets, data streams, and even scalable data streams, as described below. The SF-EAC [10] is a scalable version of F-EAC. It makes use of distributed computation to process scalable static data sets. The MapReduce programming model [9] is a scalable and reliable way to access and process data. Two main steps of SF-EAC need access to the data set: the intensification step by \(k\)-means, and the evaluation of the solutions based on the simplified silhouette index (SS) [21]. The scalable version of \(k\)-means maps each data point to its closest centroid and adjusts the centroid positions (the average of mapped data points) in a reduce job. The scalable SS version calculates the index value for each data point in a map job, while a reduce job summarizes the index score for each cluster and partition. Although SF-EAC can cluster scalable amounts of batch data and estimate \(k\), it was not designed to handle data streams directly. In this work, two algorithms based on SF-EAC are presented to cluster scalable data streams, using the algorithm to estimate the current number of clusters. Clustream [22] is designed to cluster data streams. It consists of two phases, online and offline. During the online phase, the algorithm summarizes the data in a micro-cluster structure. The algorithm keeps the micro-clusters updated as the new data points arrive incrementally. The offline phase clusters the micro-clusters instead of the raw data points since the micro-clusters summarize and represent the data points during the macro-cluster. Although Clustream is not designed for scalable data systems, nor can it dynamically estimate the number of clusters, it inspired all the proposed algorithms. FEAC-Stream [23] is a centralized data stream clustering algorithm inspired by F-EAC. After building the first clustering model using F-EAC over the initial buffer of data points, the algorithm keeps the model updated. This is done by inserting incrementally into the model each data object received from the data stream, according to its similarity to the existing clusters. The algorithm monitors the partition quality and detects when a significant change occurs. When detected, the F-EAC estimates the number of clusters and obtains a new partition. As a centralized algorithm, FEAC-Stream cannot handle scalable or distributed data streams, although its incremental update processing inspired some of our proposed algorithms. Inspired by FEAC-Stream, FEACS-ISS [12] was designed to cluster data streams with a dynamic estimation of \(k\) and scalability. It keeps the model updated by inserting the received data points incrementally in the closest cluster, while the data points lie within its SS boundary. Such a boundary is defined as the lowest SS value of an object already in the cluster, which must be inferior or equal to the SS value of the arriving data point. Otherwise, the incremental update of the model stops, and a full clustering process (using SF-EAC) is executed over the buffered data. FEACS-ISS was one of the pioneering algorithms to approach the scalable clustering of a data stream and the estimation of the number of clusters. However, it is an adaptation of a non-scalable algorithm and has sequential steps characterized as bottlenecks for processing data streams. The algorithms presented in the present work use the batch stream approach to overcome such bottlenecks. In summary, the clustering task is still challenging despite the vast body of knowledge in this task for batch scenarios and, more recently, in data streams. Most of the approaches described here are focused on the intersection between two of the three main sub-fields related to the clustering task (estimate the \(k\), MapReduce, and data streams). Recent works such as [12; 13] have addressed the intersection of these three sub-fields, proposing scalable algorithms based on centralized data stream algorithms.