Improved Deletions in Dynamic Spatial Approximation Trees
Gonzalo Navarro and Nora Reyes
The Dynamic Spatial Approximation Tree (dsa-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 dsa-tree supports
insertion and deletions of elements. However, it has been noted that deletions
degrade the structure over time, so the structure cannot be regarded as fully
dynamic in the sense that deletions are not sustainable for long periods of time.
In this paper we propose and study a new method to handle deletions over the
dsa-tree, which is shown to be superior to the former in the sense that
it does not affect search time at all. Indeed, we show that the resulting tree
is exactly as if the deleted element had never been inserted. The outcome is a
fully dynamic data structure that can be managed through insertions and
deletions over arbitrarily long periods of time without any reorganization.