Performance bounds for nearest neighbor search with k-d trees

Marco Bazzani, Sanjoy Dasgupta

The $k$-d tree is one of the oldest and most widely used data structures for nearest neighbor search. It partitions Euclidean space into axis-aligned rectangular cells. There are t…