\input{figures/pseudo-code/kd}
A KD-Tree is a binary tree where the data is split at each node based
on some dimension $d$, and a point along that axis\cite{KDTrees}. A training row $r$ is
chosen to be the splitting row for a node. Any training row who's $d$th
dimension is less than the $d$th dimension of $r$ belongs to the left
subtree, and the rest belong to the right subtree. 

Querying the KD-Tree for the nearest neighbor takes at least $O(ln(N))$
time, and can take up to $O(N)$ time for some distributions. The more
evenly the data is spread across the k-dimensional space, the closer
the runtime will be to $O(ln(N))$. If the training data is clustered in
a small subset of the space, and the testing data is not clustered in
that subset, then the majority of the space will have to be searched.
This will push the runtime closer to the worst case scenario.
