Grupos eficaces de permutantes para búsquedas por similitud

Abstract

Databases of today have different formats, very different from those contained in its infancy. Initially in a structured database information (ie numbers or words) was stored, we now have multimedia data bases (BDM) composed of pictures, music, videos, etc. In these databases the search for equality no longer makes sense, because hardly two objects are equal. A proposal for searches in databases of this type, the problem is modeled as a metric space. A metric space is a database and a function of distance between the elements is generally expensive to calculate, so the goal is to decrease the cost. The proposal raised here aims to improve one of the recent algorithms (algorithms based on permutations) in metric spaces. The main contribution is to have succeeded in reducing the number of comparisons to the original technique (up 35%) and more compact indexes without having to use more memory for index construction (up 50%).

Las bases de datos de la actualidad tienen diversos formatos, muy distintos a los que se contenían en sus inicios. En un principio en una base de datos se almacenaba información estructurada (i.e. por números o palabras), ahora tenemos bases de datos multimediales (BDM) compuestas por imágenes, música, videos, etc. En estas bases de datos la búsqueda por igualdad ya no tiene sentido, pues difícilmente 2 objetos serán iguales. Una propuesta para las búsquedas en bases de datos de este tipo, es modelando el problema como un espacio métrico. Un espacio métrico consiste en una base de datos y una función de distancia entre los elementos que generalmente es costosa de calcular, por lo que el objetivo será disminuir dicho costo. La propuesta aquí planteada pretende mejorar uno de los algoritmos recientes (algoritmos basados en permutaciones) en espacios métricos. La contribución principal es haber logrado reducir el número de comparaciones respecto a la técnica original (de hasta 35%) y tener índices más compactos sin usar mas memoria para la construcción del índice (hasta un 50%).