Aportaciones a la mejora de la eficiencia de la búsqueda del vecino más cercano

Resumen

En multitud de aplicaciones informáticas que se utilizan a diario encontramos que la búsqueda de respuestas a consultas, entre una gran cantidad de información almacenada, es un denominador común. Hace años el volumen de información con el que trabajaba una aplicación concreta era mucho más reducido que el volumen de información que se gestiona actualmente. Además de que se trabaja actualmente con mucha más información, ésta es también mucho más variada (imágenes, música, documentos). En cualquier caso, la inmediatez de la respuesta es un requisito importante cuando se realizan las consultas. En la mayoría de los casos no se requiere (o no es posible) una búsqueda por coincidencia exacta, y lo que se realiza es una búsqueda por similitud. La similitud entre dos objetos viene determinada por una función distancia definida por expertos del dominio de cada aplicación. Dado un objeto-consulta, la forma trivial de encontrar los objetos más similares a esta consulta en una base de datos consistiría en calcular la distancia entre el objeto de la consulta y cada uno de los objetos de la base de datos, lo que se conoce como fuerza bruta o búsqueda exhaustiva. En muchas aplicaciones el cálculo de la distancia puede tener un coste temporal elevado, por lo que, esta técnica tan sencilla, no es recomendable si pretendemos que el tiempo invertido en encontrar la respuesta sea el menor posible. Además, por otro lado, e independientemente del coste de la distancia, el coste temporal de esta técnica es elevado cuando el tamaño de la base de datos es muy grande. Las consultas de similitud pueden ser de varios tipos, siendo las más frecuentes la búsqueda por similitud por rango y la búsqueda del vecino más cercano. En la literatura se pueden encontrar muchos métodos para acelerar la búsqueda del vecino más cercano pero la mayoría se pueden utilizar exclusivamente cuando la información a almacenar se representa en un espacio vectorial y, la eficiencia de estos métodos, se basa en esta representación vectorial. Por otro lado, también nos encontramos diversas propuestas para espacios métricos en general, en los que los datos pueden tener cualquier tipo de representación (cadenas, grafos, árboles, etc) para los que lo único que tenemos que definir es una distancia. Estos métodos son interesantes por su generalidad, en el sentido de que, definida una distancia en el contexto de trabajo para los objetos con los que se quiere trabajar, la misma técnica puede ser aplicada a problemas muy diversos. En general, las técnicas propuestas para acelerar la búsqueda suelen almacenar en preproceso información relacionada con el problema, que normalmente será utilizada posteriormente. Durante la búsqueda, y utilizando esta información, se toman decisiones para reducir el tiempo de respuesta a la consulta realizada. El objetivo último de esta tesis es que las propuestas que se realizan sirvan para acelerar la búsqueda del vecino más cercano en espacios métricos en general. En esta tesis se analizan y proponen nuevas técnicas para la construcción de la estructuras sobre las que se almacenará la bases de datos en la que se realizará la búsqueda. En particular, las propuestas se basan en la construcción de árboles donde se analizan diferentes propiedades como la profundidad, el equilibrio, o el solapamiento entre nodos, etc para evaluar y justificar los resultados. Además, se proponen nuevas estrategias de poda en los árboles que permiten acelerar la búsqueda. Para cada una de las estrategias, se analiza el tipo de información almacenada y las ventajas de su uso y se decide en qué contextos son útiles cada una de ellas o combinaciones concretas de las mismas. Tras el análisis se propone un algoritmo que realiza combinaciones eficientes de las estrategias de poda propuestas que permiten acelerar la búsqueda. Se finaliza la tesis analizando el ámbito de aplicación de las propuestas.