Métodos de mejora del rendimiento en búsquedas por similitud sobre espacios métricos

Abstract

[Resumen] En esta tesis se abordan problemas de rendimiento de las búsquedas por similitud en espacios métricos. La búsqueda por similitud tiene como finalidad determinar los objetos más semejantes o cercanos a uno dado. Los espacios métricos permiten formalizar dicha búsqueda y han dado lugar a métodos, cuyo objetivo principal es reducir el número de evaluaciones de la función de distancia, intentando descartar el mayor número posible de objetos o de zonas que representan. Las soluciones existentes son métodos basados en pivotes, que obtienen un número reducido de evaluaciones pero requieren cantidades importantes de espacio, y métodos basados en particiones, que necesitan poco espacio pero que incrementan el número de evaluaciones. Las contribuciones de esta tesis son: i) un nuevo método basado en pivotes que reduce el tamaño del índice gracias a que almacena, para cada objeto, la distancia al pivote más prometedor para descartarlo, manteniendo un número de evaluaciones de la función de distancia que lo hacen competitivo con los métodos de particiones; y ii) una nueva estrategia para métodos basados en particiones que, reduciendo progresivamente el tamaño del cluster, disminuye significativamente el número de evaluaciones de la función de distancia, al explorar los clusters que no han sido descartados.

[Resumo] Nesta tese abórdanse problemas de rendemento das procuras por similitude en espazos métricos. A procura por similitude ten como finalidade determinar os obxectos máis semellantes ou próximos a un dado. Os espazos métricos permiten formalizar dita procura e deron lugar a métodos, cuxo obxectivo principal é reducir o número de avaliacións da función de distancia, tentando descartar o maior número posible de obxectos ou de zonas que representan. As solucións existentes son métodos baseados en pivotes, que obteñen un número reducido de avaliacións pero requiren cantidades importantes de espazo, e métodos baseados en particións, que necesitan pouco espazo pero que incrementan o número de avaliacións. As contribucións desta tese son: i) un novo método baseado en pivotes que reduce o tamaño do índice grazas a que almacena, para cada obxecto, a distancia ao pivote máis prometedor para descartalo, mantendo un número de avaliacións da función de distancia que o fan competitivo cos métodos de particións; e ii) unha nova estratexia para métodos baseados en particións que, reducindo progresivamente o tamaño do cluster, diminúe moito o número de avaliacións da función de distancia, ao explorar os clusters que non foron descartados.

[Abstract] In this thesis performance problems of similarity search in metric spaces are considered. The aim of the similarity search is to determine the most similar or closer objects to one given. The metric spaces allow to formalize this search and they have given rise to methods, whose main objective is to reduce the number of evaluations of the distance function, trying to discard the greater possible number of objects or of zones that they represent. The existing solutions are pivot-based methods, that obtain a reduced number of evaluations but require significant amounts of space; and clustering-based methods, that need little space but increase the number of evaluations. The contributions of this thesis are: i) a new pivot-based method that reduces the size of the index because it stores, for every object, the distance to the most promising pivot to discard it, maintaining a number of evaluations of the function of distance that make it competitive with clustering-based methods; and ii) a new strategy for clustering-based methods that, reducing progressively the size of the cluster, diminishes significantly the number of evaluations of the distance function when it explores the clusters that have not been discarded.