Paralelización del D-Index para búsquedas en espacios métricos aplicado a los frameworks BSP y westershed

Abstract

La gran cantidad de datos que se producen hoy en día hace que la recuperación eficiente de la información sea un problema fundamental en la ciencia de la computación. La paralelización de los algoritmos de búsqueda, diseñados originalmente para ambientes de ejecución secuencial es una manera natural de lograr la velocidad que se necesita. Un algoritmo de este tipo es el D-Index: emplea una técnica de búqueda por similitud basado en la agrupación de datos similares, siendo introducido en el 2003. El objetivo de este proyecto, que reúne a investigadores de la Universidad de San Luis (UNSL), Argentina, y la Universidade Federal de Minas Gerais (UFMG), Brasil, es la implementación de la primera versión paralela del D-Index. Actualmente estamos experimentando con varios enfoques diferentes para conseguir paralelismo. Cada enfoque difiere de los otros en la manera de dividir los datos entre los elementos de procesamiento distribuido, y cómo enviar consultas a estos elementos. Implementamos estos enfoques sobre dos modelos diferentes de ejecución en paralelo: Bulk Synchronous Parallel (BSP) y filterstream. Los experimentos preliminares muestran que cada esquema de paralelización ofrece speedup casi lineal sobre el número de procesadores.