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.