Selección efectiva de grupos de permutantes para búsquedas por similaridad en espacios métricos

Abstract

Many changes are being evident with evolution of technology, for example, there are new data types so-called: multimedia data (i.e. images, videos, etc.); one of the most important challenges is how to storage and retrieve such data. It is important to mention that searching in this kind of multimedia data only makes sense when it can be consulted by similarity, for example, a natural question is: In which pictures do I appear? Notice that is almost impossible that a picture can be taken with the same scale, and exactly at the same distance and posture. Similarity searching consists in retrieving elements from a database that are similar to a given query. One way to model this problem is to map data into metric spaces. A metric space consists of a database and a distance function, usually expensive to compute. In this thesis we present a proposal to improve one of the unbeatable algorithms in this area: permutation based algorithms. The main idea of this technique is to select a set of elements of the database (we call them permutants) and each element of the database sort them by proximity. This work is based on having a permutation of sets of permutants. Then each element of the database sort all sets by proximity. The proposal of this thesis consists in using an algorithm called SSS (Sparse Spation Selection) to form each set, as well as a new algorithm called "2near". Experiments show that using SSS improves the performance of the previous work and makes the index smaller, in which, we can get a reduction of the searching time.

La evolución de la tecnología trajo consigo cambios en todos los aspectos, por ejemplo, los nuevos tipos de datos, los llamados datos multimedia (imágenes, videos, etc.); uno de los retos más importantes es el almacenamiento y recuperación de esos datos. Note que la búsqueda en estos datos multimedia sólo tiene sentido cuando se puede consultar por similaridad, por ejemplo, una pregunta natural es ¿en qué fotografías aparezco?, considerando que es casi imposible que pueda tomarse una fotografía con la misma escala, y exactamente a la misma distancia y postura. Las búsquedas por similaridad consisten en recuperar los elementos de una base de datos que sean similares al elemento de consulta. Una manera de modelar este problema es mapeando el espacio de los datos a un espacio métrico. Un espacio métrico consta de una base de datos y una función de distancia, usualmente costosa de computar. En esta tesis se propone mejorar una de las técnicas imbatibles en esta área: algoritmos basados en permutantes. La idea general de esta técnica consiste en seleccionar un grupo de elementos de la base de datos (los llamaremos permutantes) y cada elemento de la base de datos ordena a los permutantes de acuerdo a su cercanía a éstos. Este trabajo está basado en tener una permutación de grupos, es decir, cada grupo tendrá una colección de permutantes; entonces, cada elemento de la base de datos ordenará a los grupos de acuerdo a su cercanía a éste. La propuesta de esta tesis consiste en utilizar un algoritmo llamado SSS (Sparse Spatial Selection) para la conformación de los grupos, así como un nuevo algoritmo que nombramos “2near”. Los experimentos muestran que utilizar SSS mejora el desempeño de esta técnica de grupos y hace más chico el índice, lo que produce una reducción en el tiempo de búsqueda.