# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 3 The DEALER Algorithm
### Data Partitioning
#### 3.3.1 Initial Data Partitioning  
This section introduces the initial data partitioning approach based on \(z\)-value indexing. Due to the local ordering property of \(z\)-values, points that are close in the original dataset are likely to have similar \(z\)-values. To facilitate explanation, two key concepts are introduced: local data and replicated data. As their names suggest, local data are the data inherently residing on a given node, while replicated data are data that do not originally belong to the node but are copied from other nodes due to computational requirements. These concepts are formally defined as follows:  
**Definition 4** (Local Data). : _For any sub-node \(worker_{i}\), local data are the data points on which KNN computations are performed locally on the node._  
**Definition 5** (Replicated Data). : _For any sub-node \(worker_{i}\), replicated data are data points that do not originally belong to the node but are copied from other nodes to enable the computation of KNN for the local data._  
To partition nearby data points into the same sub-node, the distributed clustering algorithm partitions the data based on the \(z\)-value information of the data objects in the dataset. The \(z\)-value contains the spatial location information of the corresponding data points, meaning that data points that are close to each other on the one-dimensional \(z\)-value axis will also be close in the original space. Furthermore, according to the DEALER algorithm, the KNN of a data point is computed using a \(z\)-value optimization method. By leveraging this property, data can be partitioned without recalculating the \(z\)-values for each data point, ensuring that points that are close in the original space are grouped into the same partition, i.e., the same sub-node. Specifically, for a given dataset \(P\), all data points are first mapped to a one-dimensional space based on the \(z\)-value transformation formula (Equation (2)), resulting in a corresponding \(z\)-value for each point. Next, it is necessary to partition all data points in the dataset into distinct subsets to facilitate further processing on different sub-nodes. Specifically, given a dataset \(P\), the data are divided into \(n\) equal parts. This is achieved by first calculating the quantile points \(\frac{1}{n^{\prime}},\frac{2}{n},\ldots,\frac{n-1}{n}\) and then partitioning the dataset into subsets \(\left(0,\frac{1}{n}\right]P,\left(\frac{1}{n^{\prime}},\frac{2}{n}\right]P, \ldots,\left(\frac{n-1}{n},1\right]P\). A sampling-based method introduced in [16] provides a straightforward approach to approximate these quantile points by sampling the data. However, this method often leads to imbalanced load distribution due to inaccuracies in the approximate quantiles. To address this issue, a sorting-based local data partitioning strategy is proposed. Since the computation of KNN points for local data on each sub-node requires sorting the data based on \(z\)-values, the proposed local partitioning strategy performs a global sorting of all data points in the dataset by their \(z\)-values. The dataset is then evenly divided into partitions, as illustrated in Figure 13.  
From Figure 13, it can be observed that after sorting the dataset based on the \(z\)-values, precise quantile points, such as \(\frac{1}{n},\frac{2}{n},\ldots,\frac{n-1}{n}\), can be easily identified. Subsequently, the entire dataset \(P\) can be uniformly partitioned into \(n\) regions either by redistributing the dataset or by utilizing the precise quantile points. Compared to sampling-based partitioning strategies, this approach introduces additional overhead due to global sorting. However, it ensures the identification of accurate quantile points, thereby achieving load balancing  
Figure 13: The illustration of the global sorting partition strategy. across the sub-nodes. In practice, global sorting is not necessarily an extra expense, as the sub-nodes must locally sort their data based on \(z\)-values during their KNN computations.