## 3 Kd-Trees
### Cut-Off Rule
A third cut-off criterion further investigates the nodes that are retained. It builds on the second criterion, by feeding \(\text{cov}_{\text{data},\mathbf{x}_{\text{rep}}}\) through a sigmoid function to yield:  
\[\text{Scov}_{\text{x}_{\text{data}},\mathbf{x}_{\text{rep}}}=\frac{1}{1+ \exp\left(-s\left(\text{cov}_{\text{x}_{\text{data}},\mathbf{x}_{\text{rep} }}-m\right)\right)} \tag{13}\]  
in which \(s\) is a steepness factor and \(m\) is a shift of the midpoint. This allows us to tune the outcome of the first two all-or-nothing criteria. Finally, it is evaluated against the relative depth of the node in the third cut-off criterion:  
\[\text{Scov}_{\text{x}_{\text{data}},\mathbf{x}_{\text{rep}}}<\frac{\text{ depth of the node}}{\text{depth of tree}} \tag{14}\]  
This way, shallow nodes are evaluated against a lower threshold, making them less likely to be retained. Lastly, whenever we encounter a node without children, a leaf, we can no longer recursively iterate further. This node is always retained. In the limit, when all the retained nodes are leaves, the kd-tree approximation results in the full set of test points. Our overall algorithm is summarized in Algorithm 1. ```
1:\(L_{\text{TN}}\)\(\triangleright\) start with an empty list of tree nodes
2:\(L_{\text{TN}}\).add(GetNodesInBranch(root)) \(\triangleright\) start recursion
3:return\(L_{\text{TN}}\)
4:procedureGetNodesInBranch(node)
5:\(L_{\text{BN}}\)\(\triangleright\) empty list of branch nodes
6:if node.isLeaf then
7:\(L_{\text{BN}}\).add(node)
8:return\(L_{\text{BN}}\)
9:else
10:if node.mustVisitChildren then\(\triangleright\) if flag set in previous iteration
11:\(L_{\text{BN}}\).add(GetNodesInBranch(node.leftChild))
12:\(L_{\text{BN}}\).add(GetNodesInBranch(node.rightChild))
13:return\(L_{\text{BN}}\)
14:else
15:for all\(\text{x}_{\text{data}}\in\text{dataset}\)do\(\triangleright\) evaluate every training point
16:if\(\text{cov}_{\text{min},\text{ max}}<\text{thres}_{\text{min},\text{max}}\)then\(\triangleright\) node too wide
17: node.mustVisitChildren\(\leftarrow\) True
18:break\(\triangleright\) no need to evaluate other training points
19:elseif\(\text{cov}_{\text{x}_{\text{data}},\text{x}_{\text{rep}}}>\text{thres}_{ \text{rep}}\)then\(\triangleright\) node too close
20: node.mustVisitChildren\(\leftarrow\) True
21:break\(\triangleright\) no need to evaluate other training points
22:elseif\(\text{cov}_{\text{x}_{\text{data}},\text{x}_{\text{rep}}}<\frac{\text{depth of the node}}{\text{depth of tree}}\), then
23: node.mustVisitChildren\(\leftarrow\) True
24:break\(\triangleright\) no need to evaluate other training points
25:endif
26:endfor
27:if node.mustVisitChildren then\(\triangleright\) recursion continues
28:\(L_{\text{BN}}\).add(GetNodesInBranch(node.leftChild))
29:\(L_{\text{BN}}\).add(GetNodesInBranch(node.rightChild))
30:else\(\triangleright\) recursion is cut off
31:\(L_{\text{BN}}\).add(node)
32:endif
33:return\(L_{\text{BN}}\)
34:endif
35:endif
36:endprocedure
```  
**Algorithm 1** Get Nodes In Kd-Tree  
In our implementation, we constructed a class named KDNode of which the most important elements are  
* references to the left and right child nodes which are also objects of the class KDNode
* a boolean indicating the node is a leaf or not
* for the leaves the position of the point
* the position of the nearest neighbour in the node to the average position, i.e., the representative point
* a boolean whether the child nodes should be visited by the algorithm
* the pre-calculated covariance between the two most distant points in the node  
We implemented a module that renders a random colour for every node returned by our algorithm. This allows for visual tuning of the kd-tree parameters. Examples of a constructed kd-tree are given in Figures 1 and 2. By tuning \(s\) and \(m\), we can tailor the kd-tree to every computational budget. Furthermore, we can have a boundary with a steepness that corresponds to the behaviour of the covariance function used.