What is a k-d tree

k-d tree is a binary-tree based data structure. It can be used for data which is k-dimensional.

What do we mean by k-dimensional?
You may have heard of 2-D and 3-D. Similarly, we have higher dimension space.

Why do we need k-d tree?
Using k-d tree we can partition a k-dimensional space into regions. This allows for efficient searching. It’s used in computer graphics and nearest neighbour searches.

How it works?
Let us consider a 2-D dataset. A point in this can be represented as <X,Y>

Constructing a k-d tree

We follow these steps to construct the tree.

1. Select a dimension and project all points along that. Example: Project all points along X-axis.
2. Take the mean of points generated along X-axis. Let’s call it X_M
3. Split using the mean. If a point X1 is < X_M then it goes to the left sub-tree else right.
4. Repeat steps 1-3 for all dimensions.

By constructing this tree we have partitioned the space into smaller regions. Given a new query point we can traverse through the Tree to find an appropriate region.

Author: Ankur

An Engineer by choice

Leave a Reply

Your email address will not be published. Required fields are marked *