Geometry and numerical algorithms · 43 / 53
K-D trees, R-trees and the dimensionality curse
Understand → trace → implement → justify
2 min reading · allow extra time for practiceA K-D tree alternates splitting axes. Balanced construction selects medians. Nearest-neighbour search visits the query side first; it must also search the other side if the splitting-plane distance is smaller than the current best distance. Pruning requires a valid distance lower bound.
Even a balanced K-D tree can take linear worst-case time for exact nearest neighbours. As dimension grows, distance concentration weakens pruning: not every KNN query is O(log n). Approximate search trades quality for speed; measure recall against an exact oracle.
R-trees index spatial objects through bounding rectangles that may overlap, forcing multiple branches to be visited. Ball trees, quadtrees/octrees and spatial hashing suit different distributions. Treating geographic coordinates as flat Euclidean coordinates can misrepresent physical distances, especially across the date line.
A worked trace
Query (4,4), best distance 3 and split x=5 give plane distance 1; the opposite branch cannot be pruned.
Cost and assumptions
Balanced low-dimensional indexes can be effective in practice; worst-case queries are O(n). A brute-force oracle costs O(nd).
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
def nearest_oracle(points, query):
return min(points, key=lambda p: sum((a-b)**2 for a,b in zip(p,query)))
assert nearest_oracle([(0,0),(5,5),(9,9)],(4,4))==(5,5)TEST YOUR UNDERSTANDING
Your turn
Why must this oracle validate equal dimensions?
Reveal the reasoning
zip truncates silently. Validate equal dimensions, nonempty input and numeric coordinates.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
MIT 6.046J · Design and Analysis ↗