\subsubsection{Cover Trees}
The Cover Tree algorithm was created by Beygelzimer et
al.\cite{CoverTrees} in 2006. It forms a tree with the top level of
the tree being of level $i$, where $i \geq $the number of levels in
the tree. Starting at the root node, as the tree is descended, $i$
decrements. At each node of the tree, the distance between any two
points of the node's children is greater than $2^{i-1}$. At least one
point $p$ in the node is within $2^i$ of any point $q$ in the node's
children.

Cover trees have a maximum insertion time of $O(c^6n ln(n))$\cite{CoverTrees}, where c is the dimensionality of the
dataset. This insertion time is theoretical and represents the worst
case scenario. While the creation time is high, the querying time is
only $O(c^{12} ln n)$. 

\subsubsection{KD-Trees}
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.

\subsubsection{Ball Trees}
Ball trees are like Cover trees, where the parent nodes contain all of
that node's children nodes. One benefit of ball trees over KD-trees
is that ball trees do not need to partition the whole
space\cite{BallTrees}. Also, the children's balls are allowed to
intersect with each other. A parent's ball is large enough to encompass
all of its children and their balls. There are two main ways to
construct the ball trees:
\bi
\item Bottom Up: The tree is constructed from the leaves to the root
  node. This provides the optimum trees, but takes the longest to
  construct.
\item Top Down: The tree is constructed from the root to the
  leaves. This provides the fastest construction time, but performs
  worse than trees generated with the Bottom Up method.
\ei
