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

  1. González Ares, Luis A.
Supervised by:
  1. Nieves R. Brisaboa Director
  2. Oscar Pedreira Director

Defence university: Universidade da Coruña

Fecha de defensa: 20 July 2012

Committee:
  1. Isidro Ramos Salavert Chair
  2. José Ramón Paramá Gabia Secretary
  3. Manuel Barrena García Committee member
  4. Gilberto Gutiérrez Retamal Committee member
  5. José Ramón Ríos Viqueira Committee member

Type: Thesis

Teseo: 329270 DIALNET lock_openRUC editor

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.