Similarity search in metric spaces on parallel multi-core and multi-GPU platforms

Resumen

Con la creciente cantidad de objetos multimedia, la búsqueda por similitud ha aparecido como un campo ampliamente estudiado en los últimos años. La similitud está dada por una función de distancia que debe satisfacer las propiedades de una métrica (positividad, simetría y desigualdad triangular). La presente tesis propone algoritmos y estrategias de distribución para resolver consultas por similitud en espacios métricos sobre diferentes plataformas paralelas. Los dos principales consultas por similitud son: consultas por rango y kNN. Una consulta por rango (q,r) recupera todos los elementos con distancia menor o igual a r de q. Una consulta kNN recupera los k elementos más cercanos a q. Debido a que la una evaluación de distancia entre dos elementos es una operación muy costosa, varios índices has sido propuestos en computación secuencial. Un índice es una estructura que almacena un conjunto de distancias claves entre elementos de la base de datos, para evitar el comparar todos los elementos de la base de datos contra la consulta. La primera parte de la tesis propone un conjunto de algoritmos sobre un servidor multi-core, utilizando como base diferentes índices usados en computación secuencial. Se encontró que una estrategia local, donde cada thread resuelve sus consultas sin comunicación con el resto de los threads, muestra los mejores resultados bajo un escenario de alta frecuencia de consultas. Por otro lado, una estrategia colaborativa, donde cada consulta es resuelta utilizando todos los threads de manera síncrona, muestra los mejores resultados bajo un escenario de baja frecuencia de consultas. Observando los resultados previos, también se propuso una estrategia híbrida, que es capaz de cambiar de una estrategia local a una colaborativa y viceversa dependiendo del tráfico actual de consultas. La segunda parte de la tesis propone un conjunto de algoritmos de mapeos y estrategias de distribución sobre un servidor single-GPU. Esta parte se dividió en dos secciones que resuelven: (1) consultas por rango, y (2) kNN. En la primera sección se proponen y comparan versiones en GPU de diferentes índices métricos utilizados en computación secuencial, y se comparan contra algoritmos de fuerza bruta en GPU, y también contra versiones multi-core. Las versiones de los índices en GPU obtienen una gran ventaja sobre las versiones multi-core. La segunda sección, usa como base las versiones previas de los índices en GPU para resolver consultas kNN. Se propone un algoritmo de búsqueda exhaustiva que supera previos trabajos del estado del arte. También, los índices obtienen mejor rendimiento sobre espacios de baja dimensión, pero sobre espacios de alta dimensión, la búsqueda exhaustiva obtiene la ventaja. La tercera parte de la tesis utiliza como plataforma un servidor multi-GPU. Esta parte se dividió en dos secciones que asumen: (1) que la base de datos cabe en memoria de la GPU, y (2) la base de datos no cabe en memoria de la GPU. En la primera sección, se proponen dos estrategias distintas. La primera estrategia propone un algoritmo de dos pasos: (1) establecer qué elementos del índice deben ser comparados contra qué consultas; (2) comparar los correspondientes elementos y consultas. La segunda estrategia propone descartar elementos y ejecutar las evaluaciones de distancia en sólo un paso, evitando sincronizaciones. Esta última estrategia muestra el mejor rendimiento. En la segunda sección, donde la base de datos no cabe en la memoria de la GPU, se propuso un nuevo índice, jerárquico multi-nivel, llamado LSC, y dos diferentes pipelines para lidiar con las transferencias de memoria entre CPU y GPU. Se compararon diferentes combinaciones utilizando diferentes índices y pipelines, y la estrategia que combina el LSC con ambos pipelines mostró el mejor rendimiento.