Fully Dynamic and Memory-Adaptative Spatial Approximation Trees
Diego Arroyuelo, Gonzalo Navarro and Nora Reyes
Hybrid dynamic spatial approximation trees are recently proposed data
structures for searching in metric spaces, based on combining the concepts of
spatial approximation and pivot based algorithms. These data structures are
hybrid schemes, with the full features of dynamic spatial approximation trees
and able of using the available memory to improve the query time. It has been
shown that they compare favorably against alternative data structures in spaces
of medium difficulty.
In this paper we complete and improve hybrid dynamic spatial approximation
trees, by presenting a new search alternative, an algorithm to remove objects
from the tree, and an improved way of managing the available memory. The result
is a fully dynamic and optimized data structure for similarity searching in
metric spaces.