Selección efectiva de permutantes como elementos clave en permutaciones extendidas para la búsqueda por similitud

Abstract

The increase in the use of information technology today generates an increasingly large amount of data. Most of them are multimedia, that is, images, videos, audios, etc. Which leads to the need to be able to search in these huge amounts of data, in addition, many times the element to be searched is not in the database but there may be very similar elements, thus the main query in this type of data they are searches by similarity; users are interested in finding similar elements, for example, a person’s face, a voice signature, fingerprints or detecting some kind of animal. One way to approach the problem is to model it as a metric space, using the database and a distance function that measures the similarity between the elements. Once modeled, a data structure called an index is created that represents an organization of the data. This paper presents a proposal to improve the performance of one of these indices, the one based on permutations. The idea is to select some elements from the database and call them permutants. The rest of the elements measures their distance from the permutants and orders them in ascending order, this order will be called permutation. The hypothesis is that elements not so close but located in a certain position may have very similar permutations or the same, what is sought is to be able to differentiate said elements by adding extra information.

El aumento del uso de la tecnología de la información hoy en día nos genera una cantidad cada vez más grande de datos. Gran parte de ellos son de tipo multimedia, es decir, imágenes, videos, audios, etc. Lo cual conlleva a la necesidad de poder realizar búsquedas en esas enormes cantidades de datos, además, muchas veces el elemento a buscar no se encuentra en la base de datos, pero sí puede haber elementos muy similares, así la principal consulta en este tipo de datos son las búsquedas por similitud; los usuarios estamos interesados en encontrar elementos similares, por ejemplo, el rostro de una persona, una firma de voz, huellas digitales o detectar alguna especie de animal. Una forma de encarar el problema es modelarlo como un espacio métrico, donde se utiliza la base de datos y una función de distancia que mide la similitud entre los elementos. Una vez modelado se crea una estructura de datos llamada índice que representa una organización de los datos. 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 no tan cercanos pero ubicados en cierta posición pueden llegar a tener permutaciones muy similares o la misma, lo que se busca es poder diferenciar dichos elementos agregando una información extra.