Improved 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 it compares favorably against alternative data structures in spaces of high dimension or queries with low selectivity. The main drawback of the sa-tree was that it was a static data structure, that is, once built, it was difficult to add new elements to it. This ruled it out for many interesting applications. We have already proposed several methods to handle insertions in the sa-tree. In this paper we propose and study a new method that is an evolution over previous ones. We show that the new method is superior to the former and that it permits fast insertions while keeping a good search efficiency.