KDTrees

A kd-tree, or k-dimensional tree, is a space-partitioning data structure for organizing points in a k-dimensional space. It is a binary tree in which each internal node corresponds to a splitting hyperplane perpendicular to one coordinate axis, dividing the space into two half-spaces. Commonly, points are stored at internal nodes, with the left subtree containing points whose value on the splitting axis is less than or equal to the node’s value, and the right subtree containing points with greater values. The splitting axis typically cycles through the k dimensions as you descend the tree, or is chosen based on data statistics such as maximum variance.

Construction, queries, and updates: kd-trees can be built by inserting points one by one or by batch construction using median splits along the chosen axis, which tends to balance the tree. Nearest neighbor search uses the splitting planes to prune parts of the search space, visiting branches that could contain closer points. Range queries and k-nearest-neighbors (kNN) queries are supported with similar pruning strategies, making kd-trees useful for proximity-based tasks.

Performance and limitations: In low dimensions, kd-trees offer efficient average-case performance for point location, nearest neighbor, and range queries. Typical complexities are around O(log n) for searches with favorable data, though worst-case performance can be O(n). The effectiveness diminishes as dimensionality grows, a phenomenon known as the curse of dimensionality. Dynamic updates such as insertions and deletions can be costly, and balanced variants or rebuild strategies are often employed. Applications include computer graphics, robotics, geographic information systems, pattern recognition, and machine learning for fast proximity search.