# Genetic Algorithms to Maximize the Relevant Mutual Information in Communication Receivers +
## 2 Preliminaries
### Flexible Parametrized Mappings
#### 3.1.2 Exact and Approximate Nearest Neighbor Clustering Using \(K\)-Dimensional Trees  
The simple nearest neighbor search approach from above has the apparent disadvantage that its complexity grows linearly with \(|\mathcal{T}|\). As a result, the simple nearest neighbor search is limited to moderate cardinalities \(|\mathcal{T}|\) in practice. Aiming for \(\mathrm{I}(\mathcal{X};\mathsf{T})\approx\mathrm{I}(\mathcal{X};\mathsf{Y})\), however, often requires quite large cardinalities \(|\mathcal{T}|\). Fortunately, so-called \(K\)-dimensional tree data structures [24; 25] can help to reduce the complexity of the simple nearest neighbor search algorithm for large \(|\mathcal{T}|\). These data structures can often determine the nearest neighbor of \(\mathbf{y}\) without explicitly calculating all possible distances \(d(\mathbf{y},\boldsymbol{\theta}_{t})\,\forall t\in\mathcal{T}\). The resulting average query complexity of a \(K\)-dimensional tree scales logarithmically with the number \(|\mathcal{T}|\) of vectors \(\boldsymbol{\theta}_{t}\), hence typically resulting in a drastic reduction of required distance calculations in comparison to the simple nearest neighbor search. It shall be mentioned, however, that the worst case complexity of a search still is \(\mathcal{O}(|\mathcal{T}|)\). \(K\) denotes the dimensionality of the data. In our case, \(K\) corresponds to the number \(N\) of inputs processed by the system from Figure 2.  
Figure 4 shows an exemplary \(K\)-dimensional tree which can be used to conduct nearest neighbor search in an exemplary set of \(|\mathcal{T}|=7\) vectors \(\boldsymbol{\theta}_{0},\boldsymbol{\theta}_{1},\ldots,\boldsymbol{\theta}_{6}\) with length \(N=3\) that we have chosen randomly for illustration purposes. We consider the task of finding the node \(\boldsymbol{\theta}_{t}\) with the smallest Euclidean distance to an exemplary query vector \(\mathbf{y}\) that is also provided in Figure 4. The true nearest neighbor of \(\mathbf{y}\) is \(\boldsymbol{\theta}_{5}\) with Euclidean distance \(d_{\mathrm{E}}(\mathbf{y},\boldsymbol{\theta}_{t})\approx 1.52\). The general principle of the search in the \(K\)-dimensional tree is that most of the explicit distance calculations are avoided and replaced by very simple threshold decisions along the axis of the data points. As it is highlighted in red in Figure 4 in the root node, the first axis considered corresponds to the first coordinate \(\theta_{t,0}\). It is easy to see that all points in the left half of the tree underneath the root node fulfill \(\theta_{t,0}\leq-1.6\) and all the points in the right half have \(\theta_{t,0}>-1.6\). As a result, for querying the first coordinate of \(\mathbf{y}\) is compared with the first coordinate of the root node. Due to the fact that \(y_{0}>\theta_{1,0}\), the query goes to the right child \(\theta_{3}\) of the root node which is indicated using the arrow labeled 1. This processing is now repeated, but in the next reached node, the axis to split is the second, i.e., \(\theta_{t,1}\), as indicated in red again. The change of the considered axis in the subsequent levels of the tree is fundamental. Figure 4: Exemplary \(K\)-dimensional tree with \(|\mathcal{T}|=7\) length \(N=3\) random vectors \(\boldsymbol{\theta}_{0},\boldsymbol{\theta}_{1}\ldots,\boldsymbol{\theta}_{6}\). The vectors are arranged according to decision thresholds given by the axis coordinate highlighted in red in the subsequent levels of the tree. Arrows indicate the processing of querying the nearest neighbor of the vector \(\mathbf{y}\). In each level, only the distances \(d(\mathbf{y},\theta_{t})\) to the visited nodes are calculated and only their minimum is stored and tracked. At node \(\theta_{3}\) we have the distance \(d_{E}(\mathbf{y},\theta_{3})\approx 2.69\) in our example. Obviously, the example query follows the path labeled 2, as \(y_{1}=-0.5>-0.6\) and the query reaches the leaf node \(\theta_{0}\). The distance to this node is \(d_{E}(\mathbf{y},\theta_{0})\approx 4.28\), so \(\theta_{3}\) stays closer.