Organizing points by space
A kd tree is a binary tree that partitions points by alternating coordinate axes. At the root you split on x, at the next level on y, and so on, cycling through the dimensions.
- Each node stores a splitting point and a cutting plane.
- The left subtree holds smaller coordinates, the right holds larger.
Choosing the median along the splitting axis keeps the tree balanced.
Searching for a neighbor
To find the nearest neighbor of a query, descend to the leaf the query would belong to, recording the best candidate distance seen. Then unwind, and at each node decide whether to explore the other side.
- If the distance to the cutting plane is smaller than the best found so far, the other branch could hold something closer, so you must search it.
- Otherwise that whole branch is pruned.
When pruning helps
In low dimensions the pruning is aggressive and search is very fast. As dimensions grow, the curse of dimensionality makes the cutting planes nearly always worth crossing, and performance degrades toward a full scan.
Key idea
A kd tree splits points on alternating axes by median, and nearest neighbor search descends to a leaf then prunes any branch whose cutting plane is farther than the current best, fast in low dimensions but weakening as dimensions rise.