Diseño y creación de medidas de disimilaridad entre permutaciones para búsquedas por proximidad

Abstract

Similarity searching or proximity searching consists in retrieving those objects that are similar of a database from a given query. Nowadays, this kind of searching is essential because there are huge digital databases where exact matching is almost impossible. Instead, the unique alternative can be the proximity searching. A strategy to solve this kind of queries is comparing all the elements in a database (sequential scan). The comparison is using a distance function which allows to measure how similar objects are. Another alternative is building an index in order to solve the query without making a sequential scan. In this work, problem is modeled as metric space (i.e. a database and a distance function) and improving an existing algorithm in order to get better processing time for answering. Our proposal consists in modify the distance function used in permutation-based algorithm (PBA) [12] in order to compare permutations. PBA works as follow, first, a set of elements are chosen (i.e. set of permutants), the rest of the database sort these permutants in increasing order, it is called permutation. Queries follows the same process and elements which permutation is similar to the query’s permutation they are part of the answer. In this work, we show that our proposal improves the PBA and contributes to the state of art.

Las búsquedas por proximidad o similaridad consisten en recuperar los elementos de la base de datos más parecidos a uno de consulta. Este tipo de búsquedas es esencial en nuestros días pues actualmente se tienen grandes volúmenes de datos digitales donde la búsqueda exacta no tiene mucha relevancia, en cambio la búsqueda por proximidad es la única alternativa. Por ejemplo, buscar la fotografía de una persona en un repositorio de imágenes, el rostro de la persona cambia con sus facciones. Una estrategia para resolver las búsquedas es comparando todos los elementos de una base datos, esto se conoce como búsqueda secuencial. Se asume que la comparación sea una función de distancia costosa y determine que tanto se parece un objeto a otro. Otra alternativa es construir un índice para hacer más eficiente esta búsqueda y evitar la búsqueda secuencial. En este trabajo, se propone modelar el problema como un espacio métrico (i.e. una base de datos y una función de distancia) y modificar un algoritmo existente para mejorar el procesamiento de la respuesta. Nuestra propuesta consiste en modificar la función de distancia empleada en los algoritmos basados en permutaciones (PBA) [12] para comparar las permutaciones. Los PBA funcionan de las siguientes maneras, seleccionan un conjunto de la base de datos (es decir, permutantes) y el resto de los elementos determina el orden de cercanía de los permutantes, a esto se le llama permutación. Las consultas siguen el mismo procedimiento y los elementos que forman parte de la respuesta serán aquellos cuya permutación es muy parecida a la de la consulta. Los resultados que presentamos en este trabajo muestran que es posible mejorar la técnica de PBA y contribuir en el estado del arte de este problema.