Spaghettis en memoria secundaria

Abstract

El Spaghettis es una estructura de datos para búsquedas por similaridad en espacios métricos (CMBY99). Esta estructura es prometedora dado que se ha demostrado que tiene buen desempeño en espacios de alta dimensión. Esta estructura es basada en pivotes y es del tipo arreglo. Una característica poco común en las estructuras métricas actuales es la manipulación de éstas en memoria secundaria. No poseer dicha característica hace poco factible la utilización de estas estructuras en aplicaciones reales. El presente trabajo describe distintas alternativas de almacenamiento en memoria secundaria para la estructura, mostrando en particular una, que resulta óptima para mantener bajos los costos de almacenamiento y acceso a disco sin disminuir los costos en términos de evaluaciones de distancia. Lo anterior permite la utilización de dicha estructura en aplicaciones reales, dado el gran tamaño de las actuales bases de datos.