Eliminación en arboles de aproximación espacial dinámicos

Abstract

El Arbol de Aproximación Espacial (sa-tree) es una estructura de datos para búsqueda en espacios métricos recientemente propuesta. Se ha mostrado que tiene buen desempeño comparada contra estructuras de datos alternativas en espacios de alta dimensión o consultas de baja selectividad. La principal desventaja que presentó sa-tree fue la de ser una estructura de datos estática, es decir, era dificultoso agregarle o eliminarle nuevos elementos una vez construida. Esto la descartaba para muchas aplicaciones interesantes. Ya hemos propuesto un buen método para manejar inserciones en el sa-tree. En este artículo proponemos y analizamos experimentalmente distintos métodos para realizar eliminaciones. Mostramos que es posible eliminar elementos en sa-tree, pagando un bajo costo por permitir total dinamismo y manteniendo a´un una buena eficiencia de búsqueda.