The Spatial Approximation Tree (sa-tree) is recently proposed data structure for searching in metric spaces. It has been shown that it compares favorably against alternative data structures in spaces of high dimension or queries with low selectivity. The main drawback of the sa-tree was that it was static data structure, that is, once built, it was difficult to add new elements to it. This ruled it out for many interesting applications. We have already proposed several methods to handle insertions in the sa-tree. In this paper we propose and study a new method that is an evolution over previous once. We show that the new method is superior to the former and that it permits fast insertions while keeping a good search efficiency.

El arbol de aproximación espacila (sa-tree) es una estructura de datos para busqueda en espacios métricos propuesta recientemente. Se ha mostrado que tiene buen desempeño comprada contra otras 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 nuevos elementos una vez construida. Esto la descartaba para muchas aplicaciones interesantes. Ya hemos propuesto varios métodos para manejar inserciones en el sa-tree. En éste articulo proponemos un método nuevo que es una evolución sobre algunos previos. Mostramos que el nuevo método es superior a los primeros y que permite inserciones rápidas mientras mantiene una buena eficiencia de búsqueda. Resumen: En este trabajo se estudia la confiabilidad de una red con dos nodos terminales s y t, tal que sus líneas están sujetas a fallas aleatorias e independientes, y la red funciona si las líneas en funcionamiento permiten la conexión de los nodos terminales a través de un camino de largo acotado por un parámetro D (que permite modelar por ejemplo una restricción en el tiempo de comunicación entre estos nodos). En particular, se da la confiabilidad de redes de topología completa (es decir, donde todo par de nodos es adyacente) y cuyas líneas pertenecen a cuatro clases de confiabilidad diferente, como una fórmula recursiva en términos de un número de nodos más pequeños y parámetro D menor. La complejidad computacional de una implementación directa de la fórmula en una red con n nodos, es de orden nD, resultando en complejidad polinómica para valores fijos de x Esto es una mejora sobre los resultados pre-existentes, dado que en general determinar la confiabilidad de redes con dos nodos terminales y parámetro D fijo, es un problema NP-difícil [2]. Además, esta fórmula recursiva puede ser utilizada para calcular el polinomio de confiabilidad (es decir, la confiabilidad como función de una única confiabilidad de líneas) de grafos completos.