KD-Trees and Ball Trees

Finding the k-nearest neighbors of a point by comparing it to every other point works fine on a few thousand rows, but it becomes painfully slow on millions. KD-trees and ball trees are ways of pre-organizing the data so a search can skip most of it entirely.

How they differ

A KD-tree splits space with axis-aligned cuts, alternating which feature it splits on at each level of the tree, roughly like organizing a phone book first by last name, then by first name within each letter. It works well in low dimensions but degrades as the number of features grows, because axis-aligned boxes stop being a good approximation of a "nearby" region.

A ball tree instead groups points into nested hyperspheres, splitting each ball into two smaller balls that together cover all its points. Because a ball's shape doesn't depend on feature axes, ball trees hold up better in higher dimensions and on data where distance isn't well captured by a box.

Drag the exponent above to see how quickly a region's "reach" grows with more dimensions — the same curse of dimensionality that erodes a KD-tree's advantage as features accumulate is why ball trees, and later approximate methods, take over for high-dimensional search.

Worked example

Searching for the nearest neighbor of a new point among 1 million 2D points, a KD-tree needs roughly log₂(1,000,000) ≈ 20 comparisons to narrow down candidates, versus 1 million brute-force comparisons — but the same data in 200 dimensions can force the tree to explore nearly every branch anyway, at which point brute force or an approximate method like locality-sensitive hashing is faster in practice.