The recently use of tech in our lives has increased the size of available data, especially those multimedia, i.e. video, images, etc. On the other hand, searching in those kind of data is imminent, moreover, the most valuable searching is by similarity; that is, users are interested in finding the most similar elements in a database, for example, I want to hum a song and retrieve the original one, or to think in a concept and retrieve the image that represent it. A way to facing the problem is modelling as a metric space, where just a database and a distance function (where similarity can be represented) is required. In this model is possible to create a data structures (called index) that represent some kind of organization in data. Nowadays there are many proposals. In this work, we propose a new index to increase the performance of one of those indexes, the permutation based algorithm. The main idea is to choose some elements in the database and called them permutants. The rest of the elements compute its distances to the permutants and sort them by proximity. This order is called permutation. The hypothesis is that equal elements has exactly the same permutation, whereas similar objects must have similar permutations. The main contribution of this work is to study the pattern to decide, for a given query, what are the possible permutations to search them.
El creciente uso de la tecnología conlleva a un aumento masivo de datos. La mayoría de éstos son de tipo multimedia, es decir, videos, imágenes, etc. La necesidad de llevar acabo búsquedas en los datos es inminente, además, la principal consulta en este tipo de datos son las búsquedas por similitud; los usuarios estamos interesados en encontrar elementos similares, por ejemplo, tararear una canción y saber a cuál corresponde, o pensar un concepto y encontrar una imagen que la relacione. Una manera de enfrentar el problema es modelarlo como un espacio métrico, donde solo se requiere la base de datos y una función de distancia que mida la similitud entre los elementos. Una vez modelado de esta forma es posible crear estructuras de datos llamados índices que representen algún tipo de organización en los datos. Actualmente existen muchos tipos de índices. En este trabajo se presenta una propuesta para mejorar el desempeño de uno de estos índices, el basado en permutaciones. La idea consiste en seleccionar algunos elementos de la base de datos y llamarlos permutantes. El resto de los elementos mide su distancia a los permutantes y los ordena de forma ascendente, a este orden se llamará permutación. La hipótesis es que elementos iguales deberían tener exactamente la misma permutación, sin embargo, elementos similares deberían tener permutaciones similares. El estudio que se presenta en esta tesis consiste en analizar el patrón para determinar, para una consulta dada, qué posibles permutaciones podrían formarse.
