A k-d tree (k-dimensional tree) is a space-partitioning binary tree data structure used for organizing points in a k-dimensional space. It is particularly useful for optimizing nearest neighbor searches, significantly improving the prediction time complexity of algorithms like k-nearest neighbors (k-NN) by continuously dividing the vector space using a divide-and-conquer approach. Each internal node represents a vector sub-space, recording a division along the $r^{th}$ dimension with a fixed threshold value and containing pointers to its two child nodes. To build the tree, a common approach is to compute the median and variance for each feature, select the feature with the largest variance, and recursively divide the dataset into two subsets based on that feature's median. For nearest neighbor retrieval, the algorithm traverses the tree to find the appropriate branch, drastically reducing the number of distance comparisons needed.