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.