# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 3 The DEALER Algorithm
### Data Partitioning
#### 3.3.2 Data Partition Adjustment  
Calculating the exact KNN points on a sub-node is a necessary condition for ensuring the accuracy of \(DCM\) and \(\rho\), as well as for ensuring the effectiveness of the clustering results. However, due to the discontinuity of the \(z\)-value curve, the global KNN points for a local data point \(p_{i}\) may not all be assigned to the sub-node containing \(p_{i}\). Therefore, it is necessary to pre-copy the information of all potential KNN points that are not stored locally from other sub-nodes. Once the data copying is completed, each sub-node only needs to compute the KNN values for its local data. Figure 14 illustrates the process of copying data points. Figure 14 illustrates the process of copying data points. In this figure, assume \(k=2\). In Partition 1, if only local data are considered, the KNN points for data point \(c\) would be points \(a\) and \(b\), which are clearly inaccurate. To accurately identify the KNN points for \(c\), the position information of point \(d\) must be copied from its original sub-node to the sub-node containing Partition 1. In this case, point \(d\) becomes a copied data point in Partition 1. Similarly, for data point \(f\), the position information of point \(g\) in Partition 3 needs to be copied to Partition 2. By following this process, each sub-node must retrieve partial data from other sub-nodes to ensure the precise computation of KNN points for its local data objects. The Z-CF algorithm accelerates the clustering process by narrowing the KNN search range through the correspondence between the original space coordinates and the \(z\)-values. However, in a fully distributed environment, the true KNN points may reside on other subnodes. Therefore, it is necessary to copy all the data information required to find the local data objects' exact KNN points from other subnodes. To minimize the communication overhead, the strategy for finding exact KNN points in a distributed environment, called S-KNN (Spark-KNN), is proposed. This strategy is based on the following two theorems:  
**Theorem 4**. : _Given a dataset \(P\), \(\forall p\in P\), \(\exists q\in P\) such that \(d(p,kp)\leq d(p,q)\), then the following holds:_  
\[z_{p^{d(p,q)-}}<z_{kp}<z_{p^{d(p,q)+}} \tag{8}\]  
_where \(kp\) is the exact k-th nearest neighbor of data point \(p\), and \(q\) is the k-th nearest neighbor found within the same sub-node as \(p\)._  
Figure 14: Illustration of the data copy. Proof. : According to Theorem 2, for \(\forall p\in P\), the following holds: \(z_{p^{d(p,q)-}}<z_{q}<z_{p^{d(p,q)+}}\) and \(z_{p^{d(p,q)-}}<z_{kp}<z_{p^{d(p,q)p+}}\). Since \(d(p,kp)\leq d(p,q)\), it follows that \(z_{p^{d(p,q)-}}<z_{p^{d(p,q)-}}\), \(z_{p^{d(p,q)+}}>z_{p^{d(p,p)+}}\). Therefore, we conclude that \(z_{p^{d(p,q)-}}<z_{kp}<z_{p^{d(p,q)+}}\). Theorem 5.2: _Given a local dataset \(P_{i}\) on any sub-node, for \(\forall p\in P_{i}\), if \(p_{0}\
otin P_{i}\) and \(d(p,p_{0})\leq d(p,q)\), the following holds_  
\[lz_{p_{i}^{d(p,q)}}<z_{p_{0}}<rz_{p_{i}^{d(p,q)}} \tag{9}\]  
_where \(q\) is the \(k\)-th nearest neighbor of point \(p\) found within sub-node \(lz_{p_{i}^{d(p,q)}}=\min\{z_{p_{i}^{d(p,q)-}}|\forall p\in P_{i}\}\) and \(rz_{p_{i}^{d(p,q)}}=max\{z_{p_{i}^{d(p,q)+}}|\forall p\in P_{i}\}\)._  
Proof. : Based on the definitions and formulas of \(lz_{p_{i}^{d(p,q)}}\) and \(rz_{p_{i}^{d(p,q)}}\), we know \(lz_{p_{i}^{d(p,q)}}<z_{p_{i}^{d(p,q)-}}\) and \(rz_{p_{i}^{d(p,q)}}>z_{p_{i}^{d(p,q)+}}\). Since \(d(p,p_{0})\leq d(p,q)\), and according to Theorem 2, the following holds: \(z_{p^{d(p,q)-}}<z_{q}<z_{p^{d(p,q)+}}\). Thus, we can conclude that \(z_{p^{d(p,q)-}}<z_{kp}<z_{p^{d(p,q)+}}\). Based on the theorems above, we propose the S-KNN strategy for accurately finding local KNN points in a distributed environment. First, we discuss how to accurately compute the KNN points for local data on a single sub-node.