Dynamic spatial approximation trees

The spatial approximation tree (sa-tree) is a recently proposed data structure for searching in metric spaces. It has been shown to compare favorably against alternative 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 rules it out for many interesting applications. In this paper we overcome this weakness. We propose and study several methods to handle insertions in the sa-tree. Some are classical 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 in 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