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.