A new methodology to solve the metric spaces search problem is presented in this work, which considers a t-spanner G'(V,E) as the metric database representation. In G', the vertices set V corresponds to the metric space objects, and the edges set E corresponds to a reduced selection of the distances between object pairs.
To achieve this goal several t-spanner construction, object insertion and deletion, t-spanner reconstruction, and object retrieval algorithms are proposed. All these algorithms are experimentally evaluated.
Finally, it is conjectured that the essential metric space property for a good t-spanner performance is the existence of element clusters, and enough empirical evidence is given to support this result. This property holds in most real-world metric spaces, so it is expected that t-spanners will have a good behavior in practice. Futhermore, it is shown that t-spanners have a great potential of applications and improvements in the field of metric spaces.
El problema de Búsqueda en Espacios Métricos o Búsqueda Aproximada consiste en encontrar los elementos de un conjunto más cercanos a una consulta dada bajo algún criterio de similitud. Este problema tiene aplicaciones en muchas áreas de las ciencias de la computación, por ejemplo: bases de datos multimediales, clasificación automática, cuantización y compresión de imágenes, recuperación de texto, biología computacional y predicción de funciones. Por otro lado, en teoría de grafos se tiene el concepto de t-spanner, que consiste en un subgrafo G' de un grafo G tal que aproxima las distancias en G con un factor de precisión t.
En este trabajo se propone una nueva metodología para resolver el problema de búsqueda en espacios métricos, la cual considera un t-spanner G'(V,E) como la representación de la base de datos métrica. En G', el conjunto de vértices V corresponde a los objetos del espacio métrico y el conjunto de aristas E corresponde a una selección reducida de las distancias entre pares de objetos.
Para cumplir este objetivo se proponen varios algoritmos de construcción de t-spanners, de inserción y borrado de objetos, de reconstrucción de t-spanners, y de recuperación de objetos. Se evalúan experimentalmente todos los algoritmos propuestos.
Por último, se conjetura que la propiedad del espacio métrico
que resulta esencial para el buen desempeño de los t-spanners
es la existencia de clusters de elementos, y se entrega suficiente
evidencia empírica que avala este resultado.
Esta propiedad se presenta en la mayoría de los espacios métricos
construidos con objetos del mundo real, por lo que se espera que los
t-spanners se comporten bien en la práctica.
Además, se muestra que los t-spanners tienen un gran potencial de
aplicaciones y mejoras en el ámbito de los espacios métricos.