Over the last 50 years, there have been many data structures proposed to perform proximity search problems on metric data. Perhaps the simplest of these is the ball tree, which was independently discovered multiple times over the years. However, there is a lack of strong theoretical guarantees for standard ball trees, often leading to more complicated structures when guarantees are required. In this paper, we present the greedy tree, a simple ball tree construction for which we can prove strong theoretical guarantees for proximity search queries, matching the state of the art under reasonable assumptions. To our knowledge, this is the first ball tree construction providing such guarantees. Like a standard ball tree, it is a binary tree with the points stored in the leaves. Only a point, a radius, and an integer are stored for each node. The asymptotic running times of search algorithms in the greedy tree match those of more complicated structures regularly used in practice.

@inproceedings{chubet23proximity,
    title = {Proximity Search in the Greedy Tree},
    author = {Oliver Chubet and Parth Parikh and Donald R. Sheehy and Siddharth Sheth},
    booktitle = {Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA 2023)},
    year = {2023}}