# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 1 Introduction
sparse cluster but erroneously merges the red and blue clusters into one. This misclassification occurs because points in sparse regions are recognized as internal points (due to the uniform distribution of \(k\)-nearest neighbors and low \(DCM\) values). For the green sparse region, this is advantageous, as density-based metrics would fail to identify it as a cluster. However, for the sparse region between the red and blue clusters, the points are incorrectly treated as belonging to a high-density region, resulting in weak connectivity. Developing an effective metric that can both accurately identify sparse clusters and alleviate weak connectivity issues is a challenge that warrants further investigation. * The Challenge In Terms Of Efficiency: The computational complexity of the CDC algorithm escalates rapidly with increasing data size, primarily due to the intensive distance computations required for determining \(DCM\) values. This substantial computational overhead renders the CDC algorithm impractical for efficiently clustering large-scale datasets in a single-machine environment. While distributed computing offers a solution by distributing the workload across multiple servers, most existing methods focus predominantly on partitioning the dataset to minimize the computational and communication costs associated with data replication or repartitioning. Nevertheless, the computational burden within each partition remains prohibitively high, as it necessitates pairwise distance calculations for all points within the group. According to the study [15], the cost of distance computations significantly surpasses that of other tasks, such as data partitioning, in distributed clustering algorithms. Consequently, there is a pressing need for an efficient distributed CDC clustering algorithm that not only ensures the assignment of similar data points to the same partition but also optimizes the computation of \(DCM\) values within each partition. To address the aforementioned challenges, a hybrid metric called \"\(DCM\) + Density\" is proposed to enhance effectiveness. Unlike traditional density-based methods, this metric does not require predefining a neighborhood radius, thereby improving the accuracy of the measurement while reducing its computational cost. For efficiency, a distributed clustering method based on \(z\)-value filtering is introduced, reducing the time complexity from \(O(n^{2})\) to \(O(n\log n)\). Our major contributions in this paper are summarized as follows:  
* We propose the \"\(DCM\) + Density\" Hybrid Metric. To accurately distinguish boundary points from core points, a hybrid metric is developed by integrating the sparsity indicator (\(\rho\)) of the region containing a data point with the cluster centralization metric (\(DCM\)) employed in the CDC algorithm. Unlike conventional density calculation methods, the computation of \(\rho\) does not require a predefined neighborhood radius. Instead, it leverages \(k\)-nearest neighbor information obtained during the \(DCM\) computation, thus reducing computational overhead. This approach not only preserves the capability to identify sparse clusters but also mitigates issues related to weak connectivity, thereby enhancing the effectiveness of clustering algorithms. * We develop a distributed direction centrality clustering algorithm enhanced by \(z\)-value indexing. This algorithm employs a \(z\)-value sorting strategy to allocate proximate  
Figure 3: Scatter plot. data points to the same processing node while pre-copying other required data points to reduce the communication cost of \(k\)-nearest neighbor calculations. Furthermore, a \(z\)-value curve-based indexing structure is designed to confine the search space to a linear range containing the query point, significantly narrowing the search scope and improving efficiency. Finally, the clustering process is completed through a \"local clustering first, cluster merging later\" approach, reducing the time complexity from \(O(n^{2})\) to \(O(n\log n)\).