[MUSIC] Let's now discuss how KD-trees can aid in
efficiently performing nearest neighbor search. So to start with, we're going to have our query point
showing with this green circle here. So this is our query point. And then the first thing we're going to do
is we're going to traverse the tree all the way down to the leaf node
that contains that query point. What that means is, we're going to check all the conditions of
this point against the conditions at each one of these internal nodes
until we get to a leaf node. Okay, so to begin with,
we're going to check the first condition, remember it was a split on x1, whether or
not it was greater than or less than 0.5. In this case, x1, for
this point, is greater than 0.5. So, we have x1 for query point, x cubed is greater than 0.5. So we say, yes, and
we traverse down this side of the tree. Then we check the next condition, and this was a condition of whether
x2 was greater than some value. I'll just call it v. So let's call this point here, v. And here we see that, yes,
x2 is greater than v. So, again, we have a yes. And we traverse down this way. And we keep doing that. And then all of the sudden
we get to a leaf note. Okay, now once we're at this leaf node, the first thing we do is start
searching for nearest neighbors. because what our hope is
is that within this box, local to our point, that might be a likely
place to find the nearest neighbor. Okay, so we compute the distances to
each point contained in this box. So this node has a list of three points,
the query point and these two other points here. And we compute those distances. So, that's what's said
right here on this slide. Now that we've computed these distances, what we do is we record the distance
to the nearest neighbor found so far. So, let's call this r. And this is distance to nearest neighbor found so far. Okay, then an actual question is,
is that it? Are we done? Does the nearest neighbor live within
the blue box that we just searched? No, not necessarily, right? That should be obvious because now
that we've drawn this fuchsia circle, we see that there are other points
that are closer to this green point that live in other neighboring boxes. So what we're going to do then is
we're going to continue searching. So we're going to go from this
node that we already examined. So that one's already done. And we're going to backtrack,
we're going to go back up the tree and start checking out other branches. Okay, so then we're going to
go down to a leaf node. So we checked this one. And now we've traversed here to this leaf. And now we're going to compute
distances to all of these points and compare relative to the distance to
our nearest neighbor found so far. And in this case, we have that distance to nearest neighbor is smaller Than what we had before. So this becomes our new nearest neighbor. And this becomes our new
distance to nearest neighbor. And then we continue searching. So, Let me just write this. This becomes our new distance
to nearest neighbor. And when we continue searching,
we've now checked this node. We've checked this node. And we're going to go and
check this other node. But what this blue box here shows
is that's the type bounding box for that node. Remember, it's the box that contains
all the points within that node. And what we see is that
the distance to that box is greater than the distance to our
nearest neighbor found so far. So, Distance to bounding box is greater than distance to nearest neighbor so far. And so what this implies,
is that we're going to prune this. We're not even going to go and compute the distance to any
point in this leaf node here. Because we know that no
point in there can be a nearest neighbor closer than the nearest
neighbor that we found so far. Okay, now what we've done. We've checked this node. We've checked this node. We've pruned this node. We go up and
we start going down this other branch. What happens here? Again, the distance to this box exceeds
the distance to our nearest neighbor, so we prune. Then what we're going to do,
is we're going to go up and start searching the other branch, but all the other boxes that we have exceed
the distance to our nearest neighbor. So, what we see is that we've been able
to prune quite a lot of the search space. Let's just go back and
look at all these points. In the brute force method, we would have had to compute
distances to all those points. But now we only had to compute distance to a very few number of data points in
this example to find our nearest neighbor. So, this is where KD-trees are so useful in performing efficient
nearest neighbor search. When you have lots and
lots of observations, especially if you're going to be
performing lots and lots of queries. Because you have to build the tree. And there's some computational
cost to building this KD-tree. But if you're going to be
using it again and again, it can actually provide
a significant savings. [MUSIC]