Dynamic Spatial Approximation Trees

Gonzalo Navarro and Nora Reyes

The Spatial Approximation Tree (sa-tree) is a recently proposed data structure for searching in metric spaces. It has been shown that the sa-tree compares favorably against other existing data structures in spaces of high dimension or queries with low selectivity. The main drawback of the sa-tree is that it is a static data structure, that is, once built, it is difficult to add new elements to it. This outrules it for many interesting applications. Our aim in this paper is to overcome this weakness. We propose and study several methods to handle insertions in the sa-tree Some are classical folklore solutions well known in the data structures community, while the most promising ones have been specifically developed considering the particular properties of the sa-tree and involve new algorithmic insights on the behavior of this data structure. As a result, we show that it is viable to modify the sa-tree so as to permit fast insertions while keeping its good search efficiency.