Aplicación de algoritmos evolutivos para indexación de objetos en espacios métricos

Abstract

[Resumen]: El principal objetivo de este trabajo es utilizar algoritmos genéticos como método de selección de conjuntos óptimos de pivotes que minimicen el cálculo de funciones de distancia necesarias durante las búsquedas de similitud sobre espacios métricos. Un buen conjunto de pivotes podrá descartar un mayor número de elementos del espacio gracias a una de las propiedades de los espacios métricos, la desigualdad triangular. Se generará una población de cromosomas representados como conjuntos de pivotes, donde cada pivote será un gen dentro del conjunto. Un conjunto será considerado mejor que otro si el promedio de funciones distancia calculadas por consulta es menor. Este método de evaluación permitirá al algoritmo genético favorecer durante la evolución de la población a aquellos conjuntos de pivotes que requieran menos cálculos promedio de la función distancia.

[Abstract]: The main objective of this work is to use genetic algorithms as a method to select optimal sets of pivots that minimize the computation of distance functions required during similarity searches in metric spaces. A good set of pivots can discard a greater number of elements from the space due to one of the properties of metric spaces, the triangular inequality. We will generate a population of chromosomes represented as pivot sets, where each pivot is a gene within the set. A set will be considered better than another if the average number of distance function computations per query is lower. This evaluation method will allow the genetic algorithm to favor pivot sets that require fewer average distance function calculations during the evolution of the population.