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

Abstract

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.