# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 3 The DEALER Algorithm
### Data Partitioning
#### 3.3.2 Data Partition Adjustment
The goal of global clustering is to merge the initial clusters generated from local clustering, ensuring that data points belonging to the same cluster are correctly grouped together. This strategy ensures that the accuracy of distributed clustering matches or approximates the accuracy of single-machine clustering results. The global clustering strategy is described in detail below. In distributed clustering, clusters are uniquely determined by their internal points. Thus, the process of cluster merging can be reduced to the merging of internal points. To determine whether two clusters from different sub-nodes need to be merged, the critical condition is whether their internal points share the same label. Specifically, for internal points belonging to two different clusters, if one internal point has no boundary points among its \(k\)-nearest neighbors (KNNs), and the other internal point is one of its KNN points, then the two clusters should be merged. Alternatively, if one internal point's KNNset includes boundary points, but another cluster has an internal point whose distance to the first point is smaller than the distance between the first point and its nearest boundary point, then the two clusters should also be merged. In other words, if clusters belonging to different sub-nodes have internal points that satisfy the conditions for being in the same cluster according to the local clustering algorithm (LE), these clusters are considered part of the same cross-node cluster. Global Clustering Strategy The specific steps of the global clustering strategy are as follows: 1. Save all internal points from the copied dataset into a separate set, \(CT\). 2. Randomly select an internal point from \(CT\). This point should retain its original cluster label from its atomic node and ensure the label differs from those on the current sub-node. Remove this point from \(CT\). 3. Check the KNN set of the selected point in the current sub-node: (1) If no boundary points exist, assign the same cluster label to all KNN points of the selected point. (2) If boundary points exist, assign the same cluster label to all points within a distance smaller than the distance to the nearest boundary point. 4. Update the cluster labels for all points whose internal point labels have changed. Ensure that all points in the same cluster share the same label. 5. Repeat the process by selecting another point from CT and applying the above steps until CT is empty. Through these iterative steps, the merging of clusters is completed. The pseudocode for the global clustering algorithm is presented in Algorithm 5. ```
0: Initial clusters \(C_{1},C_{2},\ldots,C_{m}\), sub-nodes \(slave1,slave2,\ldots,slaveM\)
0: Final clusters \(C_{1},C_{2},\ldots,C_{E}\)
1:for each sub-node \(slave\)\(i\)do
2: Copy the cluster labels of the replicated data points to the sub-node
3:\(CT=\{CDT,CDT\_Tab\}\) // \(CDT\) represents the replicated data points and \(CDT\_Tab\) represents their cluster labels
4:for each \(CDT_{i}\in CT\)do
5:\(CT\gets CT\setminus\{CDT_{i},CDT\_Tab_{i}\}\)
6: Identify other data points belonging to the same cluster according to the rules in the DEALER algorithm and update their cluster labels
7:endfor
8:endfor
```
**Algorithm 5** Global clustering

Algorithm 6 presents the pseudocode for the DEALER algorithm. The procedure begins with data preprocessing, where the input data are transformed into a one-dimensional \(z\)-value coordinate space and sorted (Lines 1-2). The sorted data are then evenly distributed across all worker nodes (Line 3). Each node independently processes its local data partition by computing the required \(z\)-value search range for all local data points, leveraging the optimized KNN search method described in Section 3 (Lines 4-7). To ensure all necessary data reside locally, the algorithm proactively replicates remote data falling within the computed range to the respective node (Line 8). The clustering process proceeds in two phases: 1.