Detección de la lista de elementos candidatos a partir de un índice invertido para la búsqueda por similitud en espacios métricos

Abstract

Similarity searching consists of retrieving from a database the elements most similar to a given query. Such searches are indispensable in multimedia databases where a sequential search is costly. One way to solve the problem is to model it as a metric space, where a distance function is required to evaluate the similarity between the elements. Algorithms that solve similarity queries in metric spaces often use indices to know the answer without having to compare the entire database. Among the existing techniques, there is the family of algorithms based on permutations, in which a set of elements is chosen, called permutants, that allow to order the rest of the elements of the database. This work focused on employing two techniques that make use of an inverted index for efficient recovery in this type of queries. The first proposal modifies both the structure of the inverted index and the distance between permutants, presented in [AS10]. While the second proposal only changes the calculation between permutants.

La búsqueda por similitud consiste en recuperar de una base de datos los elementos más parecidos a una consulta dada. Este tipo de búsquedas son indispensables en bases de datos multimedia donde una búsqueda secuencial resulta costosa. Una manera de resolver el problema es modelarlo como un espacio métrico, donde se requiere una función de distancia que evalúe la similitud entre los elementos. Los algoritmos que resuelven consultas por similitud en espacios métricos, suelen emplear índices para conocer la respuesta sin tener que comparar toda la base de datos. De entre las técnicas existentes, se encuentra la familia de algoritmos basados en permutaciones, en la que se elige un conjunto de elementos, llamados permutantes, que permiten ordenar el resto de elementos de la base de datos. Este trabajo se enfocó en emplear dos técnicas que hacen uso de un índice invertido para una recuperación eficiente en este tipo de consultas. La primera propuesta modifica tanto la estructura del índice invertido como la distancia entre permutantes, presentadas en [AS10]. Mientras que la segunda propuesta sólo cambia el cálculo entre permutantes.