Adaptación de Algoritmos para Indexamiento de Espacios Multimétricos

Abstract

Una de las operaciones más importantes en datos multimedia es la de buscar objetos similares entre sí. Para realizar esta búsqueda, es que se recurre al concepto de espacio métrico, el cual permite modelar la relación de similitud por medio de una función de distancia, que cumple la desigualdad triangular, entre otras propiedades. Esta distancia, resulta, generalmente, costosa de calcular, por lo que es necesario la construcción de índices para resolver las búsquedas de manera eficiente.

El tema de la eficacia es también un aspecto muy importante, cuando se trabaja con búsquedas por similitud, ya que no solamente es necesario poder responder las consultas rápidamente, sino que también es necesario entregar resultados relevantes. Para mejorar este aspecto, es que se utiliza un espacio multimétrico, el que define dinámicamente la distancia a utilizar, ponderando en mayor medida aquellas características que sean más relevantes para la consulta. El problema de esta estrategia es que existen pocos índices que permitan trabajar con espacios multimétricos y los índices de espacios métricos no pueden ser usados directamente, pues la distancia de éstos es fija.

Es por esta razón que en esta memoria se busca contribuir con nuevas técnicas de indexamiento para espacios multimétricos. Para esto se estudia y propone una metodología que permite adaptar índices métricos para ser utilizados en un contexto de espacios multimétricos. Se muestra también cómo esta técnica puede ser utilizada para modificar las estructuras List of Clusters y GNAT, así como también el hecho que las estructuras previamente existentes también resultan de utilizar la metodología propuesta. Finalmente se realiza una evaluación experimental, comparando los índices propuestos con los ya existentes, obteniendo que unos de los índices propuestos, MMGNAT, muestra un mejor desempeño que el estado del arte.