Data Structure Review – K-D Tree

What is K-D Tree?

A k-d tree, or k-dimensional tree, is a data structure used in computer science for organizing some number of points in a space with k dimensions. It is a binary search tree with other constraints imposed on it. K-d trees are very useful for range and nearest neighbor searches. It gives you a way to structure multidimensional data that makes range search efficiently. See this quick video to get an idea:

If you have a point A that you want to find the closest points in k dimensional space, you may need to loop thru all the points in the space and calculate the distance from A and find the shortest distance one. It is O(n) in complexity. If you structure your data using K-D tree, it will turn this into log(n) in complexity. Not only you can use it to find the closest point, you can also use the data structure to do the range search efficiently.

How to implement one?

I like this video series that shows you how to use python to find closest points in steps.

How it is used in Industry?

Lucene 6 brought a new Points datastructure for numeric and geo-point fields called Block K-D trees, which has revolutionised how numeric values are indexed and searched. According to their benchmark, Points are 36% faster at query time, 71% faster at index time and used 66% less disk and 85% less memory.

Data Structure Review – K-D Tree

log in

Use demo/demo public access

reset password

Back to
log in
Choose A Format
Personality quiz
Trivia quiz