k-d trees for spatial search

A binary search tree generalized to k dimensions. Nearest-neighbour & range queries by partitioning space.

Split space, one axis at a time

• Root splits on x, children on y, theirs on x, … (cycling axes)
• Median split → balanced, O(log n) deep, one point per cell
• Each node = a splitting plane dividing its region in two
• Build O(n log n)

Watch nearest-neighbour + pruning

Query ★ in the corner. Lines = the tree's splits. Prune: if the query is farther from a split line than from its best point, skip that whole side. Found (9,9) visiting 4 of 12 points.

The curse of dimensionality

2D: examines 0.8% (100× faster). 16D: examines 99.2% — no better than brute force.

Why high dimensions kill pruning

• Distances CONCENTRATE — nearest ≈ farthest, so best-so-far barely prunes
• A split plane depends on ONE axis; point distance on all k → plane always close
• Volume explodes → cells sparse, first guess poor
• Every exact NN structure fails ~10–20 dims → use LSH / HNSW (vector DBs)

Takeaway

Superb in low dimensions; a trap above ~10–20 (static point sets only). The curse is WHY vector databases use approximate search. Next: reservoir sampling — a fair sample of an infinite stream.