Eliminación en Arboles de Aproximación Espacial Dinámicos

Nora Reyes y Gonzalo Navarro

El Arbol de Aproximación Espacial (sa-tree) es una estructura de datos para búsqueda en espacios métricos propuesta recientemente. 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ún una buena eficiencia de búsqueda.