# 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_  
Based on _DCM_, data points are categorized as either boundary points or internal points. To achieve this, the _DCM_ values for all data points in dataset \(P\) must first be computed. The calculation method for _DCM_ values is provided in Equation (1) in Section 2.1. As indicated by the formula, the computation of _DCM_ requires identifying the \(k\)-nearest neighbors (KNNs). The primary computational cost of the DEALER algorithm lies in the distance calculations involved in finding KNN points, which represents the bottleneck that constrains the speed of the clustering process. When the dataset size becomes large, the time complexity of \(O\big{(}n^{2}\big{)}\) for these calculations becomes prohibitively expensive. Thus, improving the algorithm's speed is essential to meet the demands of large-scale data processing. To accelerate KNN searching, this section proposes a filtering strategy based on a \(z\)-value filling curve, referred to as the Z-CF (\(z\)-value-based computing filter) algorithm. Before introducing the Z-CF algorithm, we first prove two theorems. **Theorem 1**. : _In a \(d\)-dimensional space, given two data points \(p(x_{1},x_{2},\ldots,x_{d})\) and \(q(y_{1},y_{2},\ldots,y_{d})\), where \(\forall i\in[1,d]\), \(x_{i}<y_{i}\), the following holds:_  
\[z_{p}<z_{q} \tag{3}\]  
Proof. : For two data points, \(p(x_{1},x_{2},\ldots,x_{d})\) and \(q(y_{1},y_{2},\ldots,y_{d})\), where \(\forall i\in[1,d]\), \(x_{i}<y_{i}\), we refer to the method described in Lemma 4 of reference [14], which rearranges the coordinate values by alternating between the most significant bit and the least significant bit to derive the \(z\)-value of a point. This implies that \(z_{p}<z_{q}\). **Theorem 2**. : _Given two data points \(p\) and \(q\) in a \(d\)-dimensional space, if the distance between them \(d(p,q)<s\), then the following holds:_  
\[z_{p^{s-}}<z_{q}<z_{p^{s+}} \tag{4}\]  
_Here, \(p^{s-}\) and \(p  
it is necessary to first identify the potential range for the KNN points, then compute the distances within that range and sort the points to obtain the exact KNN. Building on the two theorems mentioned above, after arranging the data points in ascending order based on their \(z\)-values, we can efficiently identify the KNN points for any given data point \(p\). This is achieved by iteratively searching in both forward and backward directions along the \(z\)-value axis, selecting the closer of the two candidate points at each step. After \(k\) iterations, we obtain a point \(kp\), and it follows that the distance \(d(p,kp)\) is necessarily greater than the farthest distance among \(p\)'s true KNN points. According to Theorem 2, the positions of \(p\)'s KNN points along the \(z\)-value axis fall within a specific range. Furthermore, Theorem 2 establishes that \(p\)'s KNN points must lie within a neighborhood centered at \(p\) with a radius of \(d(p,kp)\) after \(k\) comparisons. Within this defined range, an exact KNN search can then be conducted. Compared to traditional KNN searches, incorporating the \(z\)-value index significantly reduces the search space by narrowing the potential candidate set from the entire dataset to a localized subset. This approach substantially decreases the number of distance computations required, thereby improving computational efficiency. The detailed strategy and analysis are presented as follows. First, identify the initial potential KNN points. For a given \(d\)-dimensional dataset \(P\), all data points in the dataset are mapped into one-dimensional space via the \(z\)-value filling curve so that the \(z\)-value coordinates correspond one-to-one with the original space coordinates. Next, the data points are sorted by their \(z\)-values. On the \(z\)-value axis, the initial potential KNN points are identified. For any data point \(p\), search for one point in each direction along the \(z\)-value axis: one in the positive direction, denoted \(p_{1+}\), and one in the negative direction, denoted \(p_{1-}\).