Keywords
kd tree, NN search, Spatial partitioning

Technologies
Python, JavaScript, HTML/CSS, Matplotlib

A k-d tree is a data structure for organising points in multi-dimensional space, first introduced by Jon Louis Bentley in 1975. Rather than scanning every record to answer a query, it recursively partitions space using splitting hyperplanes, allowing large portions of the dataset to be eliminated without ever being examined. This project involved a full self-study and implementation of the k-d tree from Bentley's original paper.

The implementation, written in Python, covers insertion, exact search, partial search, region queries, nearest neighbour search, deletion, and rebalancing. Two nearest neighbour algorithms were implemented and compared: Bentley's original approach, and an improved version using bounding box pruning. Benchmarking against a brute-force baseline revealed a 1900x speedup at two dimensions, collapsing to below brute-force performance by fifteen dimension. A clear example of the curse of dimensionality. An interactive web visualiser was also built, allowing users to insert points, watch the space get partitioned in real time, and see which branches of the tree get explored versus pruned. Come find the demo on open day.