Estructuras sucintas para búsquedas en espacios métricos: Spaguetti

Abstract

In this paper a modification to the proposed algorithm Spaghetti [ Chávez González, 1999 , Chavez et al. , 1999]. The new structure aims to reduce the space required for storage and compute fewer comparisons in the intersection between the sets , key in the implementation process of Spaghetti . To achieve the stocking trade between elements of a database with a set that identifies and order these items index is restructured , this eliminates the dependence between the candidate lists of each existing pivot in the original structure and Spaghetti to change the order in which the sets intersect. SVS , small against small , intersecting sets in ascending order by their cardinal Two different strategies were tested. Random calculates the intersection of the sets by selecting randomly , using the joint probability that an item should be removed remain on the list of candidates with the iterative forward method .

En el presente trabajo se propone una modificación al algoritmo Spaghetti [Chávez González, 1999, Chávez et al., 1999]. La nueva estructura tiene como objetivo reducir el espacio necesario para almacenarse y calcular en menor número de comparaciones la intersección entre los conjuntos, proceso clave en la ejecución del Spaghetti. Para lograrlo se reestructura el índice almacenando la permutación que existe entre los elementos de una base de datos con un conjunto que identifica y da orden a estos elementos, esto elimina la dependencia entre las listas de candidatos de cada pivote existente en la estructura original Spaghetti y permite cambiar el orden en que se intersectan los conjuntos. Se probaron dos estrategias diferentes: SVS, pequeño contra pequeño, intersecta los conjuntos en orden ascendente por su cardinal. Aleatorio, calcula la intersección de los conjuntos seleccionando el orden de forma aleatoria, aprovechando la probabilidad conjunta de que un elemento que debe ser eliminado permanezca en la lista de candidatos con el avance iterativo del método.