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.