Memory-Adaptative Dynamic Spatial Approximation Trees
Diego Arroyuelo, Francisca Muñoz, Gonzalo Navarro and Nora Reyes
Dynamic spatial approximation trees (dsa-trees for short) have shown to
be suitable data structures for searching in high dimensional metric spaces.
However, if sufficient storage space is available, pivoting schemes beat
dsa-trees in any metric space. In this paper we present new data
structures for proximity 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 a dsa-tree
and able of using the available memory to improve the query time.
We study the problem of making the best possible use of the available memory.
We show experimentally that our data structures are competitive choices for
searching in metric spaces.