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.