# Heterogeneous Distributed Big Data Clustering on Sparse Grids
## 4 Other Steps
### Computing the \(k\)-Nearest-Neighbor Graph  
To create the \(k\)-nearest-neighbor graph, we have developed an approximate variant of the \(\mathcal{O}((k+d)m^{2})\) algorithm that compares all pairs of data points. Instead of creating a neighborhood list with \(k\) entries directly, we employ an approach with \(b\) bins that implicitly splits the dataset into \(b\) ranges. For every data point \(i\) the dataset is iterated. Thereafter, each bin contains the nearest neighbor of its assigned range of data points. To obtain an approximate \(k\)-nearest-neighbor solution, the \(k\) indices with the smallest associated distances are selected from the \(b\) bins. Pseudocode for this approach is displayed in Algorithm 3.  
```
Input : dataset \(T=\{\mathbf{x}_{i}\in[0,1]^{d}\}_{i=1}^{m}\) Output :\(k\)-nearest-neighbor graph \(g\) as neighborhood list for\(c=1\dots b\)do \(\operatorname{dists}_{c}\leftarrow\infty\) for\(i=1\dots m\)do \(c\gets 0\)//\(c\)iterates over the number of bins for\(j=1\dots m\)do \(\operatorname{dist}\leftarrow\operatorname{distance}(\mathbf{x}_{i},\mathbf{x}_{j})\)//iterates\(d\) if\(dist<\operatorname{dists}_{c+1}\)then \(\operatorname{bins}_{c+1}\gets j\) \(\operatorname{dists}_{c+1}\leftarrow dist\) \(c\leftarrow(c+1)\) mod \(b\) \(g_{i}\leftarrow\operatorname{extract\_nearest\_k}(\operatorname{dists}, \operatorname{bins},i)\)
```  
**Algorithm 3**A variant of the \(\mathcal{O}(m^{2})\)\(k\)-nearest-neighbor algorithm that uses \(b\) bins.  
This \(k\)-nearest-neighbor algorithm offers several advantages. It is not affected by the issue of dimensionality and therefore, works well for the higher-dimensional datasets we target. In contrast, spatial partitioning approaches such as \(k\)-\(d\)-trees tend to suffer from the issue of dimensionality. Furthermore, it maps well to modern hardware architectures as it is straightforward to parallelize and vectorize. Through cache blocking of the outer loop that iterates \(i\), the resulting algorithm is highly cache-efficient as well. Finally, the number of neighbors \(k\) and the number of bins \(b\) are the only parameters to specify.  
Binning was introduced for performance reasons. It allows us to only perform a single comparison in the innermost loop instead of \(k\) comparisons and, therefore, reduces the complexity to \(\mathcal{O}(dm^{2})\). The effect on the detected clusters is minimal, as it is very likely that nodes are still connected to close-by nodes of the same density region and therefore, the same cluster. Furthermore, edges that intersect low-density regions get pruned, as we describe in the next section.  
The overall clustering algorithm is relatively robust with regard to different values of \(k\). However, \(k\) should not be too small. Otherwise, the \(k\)-nearest-neighbor graph might be split into more connected components than are desired. For larger values of \(k\), performance decreases slightly in the subsequent pruning step as the pruning algorithm has linear complexity in \(k\). In our experience, choosing \(k\) with values between five and ten balances this trade-off. Consequently, we set \(b\) to 16, as it is larger than expected values of \(k\) and leads to a good-enough approximation of the \(k\)-nearest-neighbor graph. On modern hardware platforms, this choice of \(b\) should not increase the cache or register memory requirements of the algorithm to an extent that would affect performance.