Entre los algoritmos para buscar objetos en un EM, AESA (Approximating Eliminating Search Algorithm) es uno de los que presenta mejor desempeño. El problema de AESA es que requiere precalcular y almacenar las n(n-1)/2 distancias entre pares de objetos, necesitando O(n2) memoria, lo que lo hace impracticable. Sin embargo, si fuese posible disminuir el uso de memoria de AESA, éste se podría utilizar en aplicaciones reales. Con esta intención, se considera la alternativa de utilizar t-spanners para representar la estructura de distancias entre objetos del EM, conformando de este modo la base de datos métrica.
Durante la tesis se desarrollaron cinco algoritmos de construcción de t-spanners, un algoritmo de inserción y otro de borrado de objetos en el t-spanner, un algoritmo reconstrucción de t-spanners y un algoritmo para resolver consultas de recuperación de objetos. Adicionalmente se realizaron experimentos de construcción de t-spanners en EMs de interés, vale decir, espacios vectoriales con la distancia euclidiana, espacios de strings con distancia de edición y espacios de documentos con la distancia coseno. También se realizaron experimentos de búsqueda en dichos EMs, comparando el método basado en t-spanners contra AESA y contra un algoritmo basado en pivotes.
En EMs construidos con objetos del mundo real, se muestra que el método basado en t-spanners presenta resultados mucho mejores que los obtenidos con algoritmos basados en pivotes, y por otro lado, que es altamente competitivo con respecto a AESA. Por ejemplo, en el espacio de los documentos, utilizando el método basado en t-spanners, se requiere de un 3.84 % de la memoria que utiliza AESA y se paga un exceso de sólo un 9 % más de las evaluaciones de distancia que utiliza AESA para recuperar objetos. Se conjetura y demuestra experimentalmente que la propiedad del espacio métrico que resulta esencial para el buen comportamiento de los t-spanners, es la existencia de clusters de elementos. Esta propiedad se presenta en la mayoría de los espacios de la vida real, por lo que se espera que los t-spanners se comporten bien en la práctica.
Además de los resultados concretos de esta tesis, se abre la puerta a varios temas futuros de investigación. Uno es el desarrollo de algoritmos de construcción de t-spanners que consideren valores de t dependientes de la distancia entre los nodos, de manera que la aproximación sea mejor para la vecindad de los nodos que para los nodos alejados. Otro es utilizar el t-spanner como una estructura de navegación sobre el EM. De esta manera se podría considerar la búsqueda como la combinación de una fase de acercamiento hacia la consulta, y luego una fase de eliminación de candidatos.