K-D Trees

One way we can extend the hierarchical partitioning idea to dimensions greater than two is by using a K-D Tree. It works by rotating through all the dimensions level by level.

So for the 2-D case, it partitions like an X-based Tree on the first level, then like a Y-based Tree on the next, then as an X-based Tree on third level, a Y-based Tree on the fourth, etc.

In the first graphic, you can see how each level is partitioned. In the one below, you can see the nodes of the tree in relation to one another in the 2-D space. Note when you are running operations on a K-D Tree or quadtree, you should be thinking about the tree structure (1st image) and not the 2-D space (2nd picture) because only the tree holds information about the levels.

For the 3-D case, it rotates between each of the three dimensions every three levels, and so on and so forth for even higher dimensions. Here you can see the advantages in a K-D Tree in how it is more easily generalized to higher dimensions. But, no matter how high the dimensions get, a K-D tree will always be a binary tree, since each level is partitioned into "greater" and "less than".

For a demo on K-D tree insertion, check out these slides

We can break ties by saying that items equal in one dimension should always fall the same way across the border. (For example, an item equal in the x-dimension to its parent node will always fall to the right of the partition.)

Nearest Neighbor using a K-D Tree

To find the point that is the nearest neighbor to a query point, we follow this procedure in our K-D Tree:

• Start at the root and store that point as the "best so far". Compute its distance to the query point, and save that as the "score to beat". In the image above, we start at A whose distance to the flagged point is 4.5.
• This node partitions the space around it into two subspaces. For each subspace, ask: "Can a better point be possibly found inside of this space?" This question can be answered by computing the shortest distance between the query point and the edge of our subspace (see dotted purple line below).

• Continue recursively for each subspace identified as containing a possibly better point.
• In the end, our "best so far" is the best point; the point closest to the query point.

For a step by step walkthrough, see these slides

Summary and Applications

See the video above for a summary of this chapter, and some interesting applications of the presented data structures.