A Comparative Analysis of Data Structures for Dynamic Nearest Neighbour Search

Nearest-neighbour search is a fundamental problem in computer science with applications in spatial databases, geographic information systems, machine learning, and similarity search. This project investigates the performance of four approaches to exact nearest-neighbour search in two-dimensional space: Brute Force, KD-Trees, Quadtrees, and Spatial Hashing. Static implementations were developed and evaluated using uniformly distributed and clustered datasets of increasing size. Dynamic implementations were also developed, including initial rebuild-based approaches and more efficient versions designed to reduce update costs. These were evaluated under query-heavy, balanced, and update-heavy workloads containing insertions, deletions, updates, and nearest-neighbour queries. Parameter experiments were also performed to examine the effects of Quadtree node capacity and Spatial Hash cell size. Correctness was validated against Brute Force, while performance was evaluated using query time, update time, total workload time, and memory usage. The results showed that no single approach was best under all conditions. KD-Trees provided particularly strong static query performance on uniformly distributed data but were more affected by clustering and dynamic updates. Quadtrees provided more consistent performance across spatial distributions, while Spatial Hashing performed particularly well under dynamic workloads when appropriate cell sizes were used. Brute Force had minimal structural memory overhead but scaled poorly for large static datasets. Overall, the results demonstrate that the most suitable nearest-neighbour approach depends on spatial distribution, workload characteristics, parameter selection, and the trade-off between execution time and memory usage.