k-d Tree#
\(k\)-\(d\) tree is a space-partitioning binary tree [Bentley80], where
Each non-leaf node induces the hyperplane that splits the feature space into two parts. To define the splitting hyperplane explicitly, a non-leaf node stores the identifier of the feature (that defines axis in the feature space) and a cut-point
Each leaf node of the tree has an associated subset (a bucket) of elements of the training data set. Feature vectors from a bucket belong to the region of the space defined by tree nodes on the path from the root node to the respective leaf.