Skip to main content
Definition Website Computer and Technology

K-D Tree

Subject: Computer and Technology noun /ˈkeɪˌdiː ˈtriː/ 1 definition

  1. Definition (noun)

    Entry #284 · Updated

    A K-D Tree (k-dimensional tree) is a space-partitioning binary search tree that organizes points within a k-dimensional Euclidean space. Each node defines an axis-aligned splitting hyperplane along one coordinate dimension, partitioning points with smaller values along that axis into its left subtree and points with equal or larger values into its right subtree. By cycling through the k coordinate axes by depth or splitting along the dimension of widest spread, the tree accelerates orthogonal range searches and k-nearest neighbor (k-NN) queries by pruning entire subtrees whose bounding regions cannot contain matching or closer points. While balanced K-D Trees achieve O(log n) average lookup time in low-dimensional geometry, pruning efficiency degrades toward linear O(n) scans in high-dimensional spaces due to the curse of dimensionality, where approximate indexes such as HNSW or LSH are typically preferred.

    Common Types

    • Standard Median-Split K-D Tree: Stores a data point at every node and cycles splitting axes by depth (depth mod k), choosing the median point along each axis during static construction to maintain balanced O(log n) tree height.

    • Bucket K-D Tree: Keeps only split axes and threshold values in internal routing nodes while storing points inside fixed-capacity contiguous leaf arrays, reducing tree depth and improving CPU cache locality during queries.

    • Sliding-Midpoint K-D Tree: Splits a region along its longest bounding-box axis at the geometric midpoint—sliding the hyperplane to the nearest point if one half would be empty—to prevent elongated cells on clustered or skewed datasets.

    • Randomized K-D Tree Forest: Builds an ensemble of K-D Trees that each split along a randomly chosen high-variance coordinate dimension, enabling fast approximate nearest-neighbor search in higher-dimensional feature spaces.

    Example

    A robotics perception pipeline indexes 500,000 3D LiDAR coordinates (x, y, z) in a scipy.spatial.KDTree configured with leafsize=16 to detect nearby obstacles. When the planner calls query_ball_point([12.4, -3.8, 0.9], r=0.5) around a rover's chassis, backtracking skips any subtree whose axis-aligned bounding box lies farther than 0.5 meters from the query point, evaluating only nearby leaf buckets instead of scanning all 500,000 coordinates.