# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 3 The DEALER Algorithm
### Computation of DCM and \(\rho\) for Local Clustering
#### 3.2.1 Computation of _Dcm_
The distances between \(p\) and these two points, \(d(p,p_{1+})\) and \(d(p,p_{1-})\), are calculated. The point with the smaller distance is selected as the first initial KNN point. Then, along the direction of the closer point on the \(z\)-value axis, search for the second point, calculate the distance, and compare it with the previously identified farther point. The point with the smaller distance is selected as the second initial KNN point, and this process continues until \(k\) points are identified. Next, determine the potential range for the KNN points. For any given data point \(p\), the initially identified KNN points are sorted in ascending order of distance. The point that is the \(k\)-th closest, denoted as \(kp\), is selected. The potential range for the KNN points is defined as a neighborhood centered at \(p\) with a radius of \(d(p,kp)\). As illustrated in Figure 9, instead of performing a search over the entire data space, a one-dimensional linear search within the interval \(\left(z_{p^{\mu(p,kp)-}},z_{p^{\mu(p,kp)+}}\right)\) is sufficient to identify the KNN points of data point \(p\). This is because, for any data point \(q\) such that \(d(p,q)<d(p,kp)\), according to Theorem 2, the \(z\)-value of \(q\) must lie within the interval \(\left(z_{p^{\mu(p,kp)-}},z_{p^{\mu(p,kp)+}}\right)\). Therefore, there is no need to compute the distances from \(q\) to \(p\) for the ranges where \(z_{q}\geq z_{p^{\mu(p,kp)+}}\) or \(z_{q}\leq z_{p^{\mu(p,kp)-}}\), as it is guaranteed that \(d(p,q)\) will be greater than \(d(p,kp)\). It is important to note that if, for data points \(p\) and \(q\), the \(z_{q}\) lies within the interval \(\left(z_{p^{\mu(p,kp)-}},z_{p^{\mu(p,kp)+}}\right)\), and the \(z_{p}\) lies within the interval \(\left(z_{q^{\mu(p,kp)-}},z_{q^{\mu(p,kp)+}}\right)\), then when calculating the KNN for data point \(p\), the distance \(d(p,q)\) needs to be calculated once. Similarly, when calculating the KNN for data point \(q\), the distance \(d(q,p)\) must also be calculated once. This results in redundant distance calculations and increases unnecessary computational overhead, as illustrated in Figure 10.  
Figure 9: The illustration of the linear search range. To optimize the computational strategy and reduce unnecessary overhead, this study adopts a one-sided computation approach. Specifically, for a given data point \(p\), we calculate the distance only to the points on one side of the interval. This means either computing the distance to the data points in the right-hand interval \(\left(z_{q},z_{p^{(p,p)p}+}\right)\) or to those in the left-hand interval \(\left(z_{p^{(p,p)p}-},z_{q}\right)\). Both methods yield the same result, and in this paper, the first method is employed, as shown in Figure 11.  
The proposed strategy is based on Theorem 3. Theorem 3.: _Given a dataset \(P\) and any data point \(p\), suppose there exists a subset \(Q_{p}\subset P\) such that for \(\forall q\in Q_{p}\), \(d(p,q)<s\). The subset \(Q_{p}\) is then divided into two subsets, denoted as \(Q_{p^{-}}\) and \(Q_{p^{+}}\), where \(Q_{p^{-}}\cup Q_{p^{+}}=Q_{p}\). For \(\forall q\in Q_{p^{-}}\), \(z_{q}<z_{p}\), and for \(\forall q\in Q_{p^{+}}\), \(z_{q}>z_{p}\). Then, we have the following:_  
\[\forall q\in Q_{p^{-}},z_{p^{+-}}<z_{q}<z_{p} \tag{5}\]  
\[\forall q\in Q_{p^{+}},z_{p}<z_{q}<z_{p^{+}} \tag{6}\]  
Proof. : According to Theorem 2, for all \(\forall q\in Q_{p^{+}}\), we have \(z_{p^{-}}<z_{q}<z_{p^{+}}\). Since \(z_{p}<z_{q}\), it follows that \(z_{p}<z_{q}<z_{p^{+}}\), thus proving Equation (6). A similar argument can be applied to prove Equation (5). Based on Theorem 3, when calculating the distance between data point \(p\) and data point \(q\), if \(z_{p}<z_{q}<z_{p^{+}}\), we can compute the distance from \(p\) to \(\forall q\in Q_{p^{+}}\). Similarly, when calculating the distance from \(p\) to \(\forall q\in Q_{p^{-}}\) with respect to their previous data points in the interval \(\left(z_{q},z_{q^{+}}\right)\), we can compute the distance from \(p\) to all \(\forall q\in Q_{p^{-}}\).