# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 3 The DEALER Algorithm
### Data Partitioning
#### 3.3.2 Data Partition Adjustment
Local clustering: Each node executes the base clustering algorithm on its local data to generate initial clusters (Line 9). 2. Global cluster merging: The initial clusters from all nodes are aggregated and merged to produce the final global clustering result (Line 10). ```
0: Data set \(P\), KNN value \(k\), \(DCM\) threshold \(T_{DCM}\), number of nodes \(M\)
0: All clustering in the dataset \(P\): \(\{C_{1}\}\), \(\{C_{2}\},\ldots,\{C_{n}\}\)
1: all the data points \(p_{i}\) in the dataset \(P\) into one-dimensional space, obtain \(z_{p_{i}}\)
2: Sort the number of points according to the value of \(z\) from smallest to largest```
1:According to the number of nodes, divide the data points on the axis of the \(z\) value into M equallities and assign them to the corresponding node \(M_{j}\)
2:for each data point \(p\) in \(M_{j}\)do
3: Compute \(z_{p^{(l,p)p}-z},p^{(l,p)p+}\)
4:endfor
5: Calculate \(\max\{z_{p^{(l,p)p}+}|p\in M_{j}\}\) and \(\min\{z_{p^{(l,p)p}-}|p\in M_{j}\}\)
6: Copy data that is not on node \(M_{j}\) in the interval \((\min\{z_{p^{(l,p)p}-}|p\in M_{j}\})\), \(\max\{z_{p^{(l,p)p}+}|p\in M_{j}\})\) with \(z\) values to \(M_{j}\)
7: Execute Algorithm 4 on node \(M_{j}\) to locally cluster to form the initial cluster
8: Run Algorithm 5 to complete the global clustering
```

**Algorithm 6**_Cont._

### Time Complexity Analysis

The computational cost of the DEALER algorithm primarily arises from the distance calculations required to identify the \(k\)-nearest neighbors (KNNs). This step is also the main bottleneck limiting the speed of the clustering algorithm. Before determining the potential range for KNN, the algorithm uses \(z\)-value indexing to map all data points in the dataset onto a one-dimensional coordinate axis and sort them. This step incurs a computational cost of \(O(n\log n)\). Next, when calculating the potential range for KNN, the algorithm first identifies the initial KNN points on the \(z\)-value coordinate axis. This is performed using a linear search. Since the search requires moving left and right to find \(k\) potential KNN points, the algorithm computes the distance between the current data point and \(k+1\) other points and performs comparisons. This step has a cost of \(O(2 kn+2n)=O(kn)\). Following this, the precise KNN search range is determined based on the relationship between the \(k\)-th nearest neighbor and the current data point. This computation incurs an additional cost of \(O(2n)\). Finally, the algorithm calculates the distance between the current data point and every data point within the determined search range. These data points are those whose \(z\)-values fall within the interval \(\left(Z_{d(p,q)^{-}},Z_{d(p,q)^{+}}\right)\), where \(p\) is any data point in the dataset, and \(q\) is the \(k\)-th nearest neighbor of \(p\) in the initial KNN set. This step also incurs a cost of \(O(kn)\). In most cases, \(k\ll n\), meaning that \(k\) is significantly smaller than \(n\). In summary, the overall time complexity of the DEALER algorithm is \(O(n\log n)\). ## 4 Discussion

Our enhancements to the CDC algorithm primarily focus on two key dimensions: clustering effectiveness and computational efficiency. (1) Effectiveness Enhancement: To improve clustering quality, we developed a hybrid metric integrating _DCM_ with local density (\(\rho\)). This integration builds upon CDC's original _DCM_ cluster centrality metric while incorporating regional density estimation for precise core/boundary point differentiation. The proposed two-step filtering mechanism operates as follows:

Primary screening using _DCM_ values

Secondary refinement through \(\rho\)-density evaluation

This dual-filter approach maintains sensitivity for sparse cluster detection while effectively mitigating weak connectivity issues. Unlike conventional density computation requiring predefined neighborhood radii, our method innovatively derives \(\rho\)-values directly from k-nearest neighbor (KNN) information generated during _DCM_ calculation.