P-DIndex: Optimizando las búsquedas sobre espacios métricos

Abstract

Para reducir los costos de búsqueda y acelerar los tiempos de respuestas sobre grandes colecciones de datos se utilizan índices que particionan los datos en subconjuntos de manera tal que las respuestas a las consultas pueden ser evaluadas sin examinar exhaustivamente toda la colección. A medida que crece la complejidad de los tipos de datos modernos los espacios métricos obtienen mayor popularidad como paradigma de recuperación de información. Un índice propuesto recientemente es el D-Index el cual es una estructura de múltiples niveles que permite dividir recursivamente los objetos del espacio métrico en conjuntos separables. Este índice combina técnicas de clustering y técnicas basadas en pivotes para realizar las búsquedas por similitud. Por otro lado, la resolución de consultas sobre este tipo de índices tiende a ser muy costosa por la dificultad que implica la ejecución de la función de similitud, la cual depende del tipo de objeto multimedial utilizado (video, sonido, imagen, etc.). La computación paralela es un paradigma que permite reducir los tiempos de ejecución de los algoritmos. Existen dos escuelas referentes a la comunicación en un diseño paralelo: síncrona y asíncrona. En particular en este trabajo utilizamos el modelo de computación paralela síncrono Bulk-Synchronous Parallel - BSP que provee un modelo de costo sencillo que permite predecir los tiempos de ejecución de los algoritmos paralelos.