Desarrollo de algoritmos paralelos de “Búsqueda del Vecino más Lejano”

Abstract

[Resumen] El algoritmo de la Búsqueda del Vecino más Lejano se está usando cada vez con mayor frecuencia dentro del campo del Aprendizaje Automático para encontrar el elemento con mayor distancia a otro en un conjunto de elementos similares. Uno de sus usos principales es en plataformas de e-commerce y streaming, que con la situación de pandemia han pasado a ser empleadas diariamente por una gran parte de la población. Para que estas plataformas logren mantener a su base de clientes interesada en nuevos productos es muy importante que dispongan de un sistema de recomendaciones que logre cumplir las expectativas del cliente y pueda ofrecer productos que puedan interesarle. La técnica de la Búsqueda del Vecino más Lejano permite la recomendación de productos similares a los ya consumidos sin que el cliente sienta que se le recomienda lo mismo de forma repetida. El problema que representan estos algoritmos de búsqueda de vecinos es su larga duración si queremos obtener un resultado exacto, mucho más teniendo en cuenta que en la actualidad estamos viviendo la explosión del fenómeno Big Data, donde las bases de datos se vuelven mayores. El trabajo realizado en Este Trabajo de Fin de Grado consiste en la paralelización de los algoritmos de búsqueda de vecinos desarrollados para la librería MLPack, debido a la eficiencia que los mismos demuestran en su formato secuencial. Se ha utilizado la técnica de descomposición de dominio para distribuir la carga de trabajo en un clúster de computación de altas prestaciones multinodo y esta decisión ha llevado al desarrollo de dos implementaciones distintas dependiendo de si descomponemos el conjunto de consulta o el de referencia. Para coordinar la paralelización entre los nodos se ha utilizado MPI como interfaz de paso de mensajes. El código está disponible en GitHub1. Se han realizado pruebas de rendimiento de ambas implementaciones en un clúster con 8 nodos, 64 GB de memoria y 16 núcleos por nodo (128 núcleos en total) y se han obtenido resultados muy satisfactorios para los conjuntos de datos escogidos, con aceleraciones de hasta 114x.

[Abstract] The Furthest Neighbor Search algorithm is becoming extremely popular in the field of Machine Learning in order to find the element which has the longest distance to another in a set of similar elements. One of its main uses is in e-commerce and streaming platforms, which have become of daily use by a large majority of the population due to the pandemic 1 https://github.com/Erivos/ParallelNeighborSearch situation. In order to keep their client base interested in new products these platforms must keep a good recommendation system able to accomplish the expectations of the clients and offer products that are of interest to them. The Furthest Neighbor Search allows the recommendation of products similar to the ones already consumed, but without making the client feel that the same items are repeatedly recommended. The problem associated to these search algorithms is their long computational time if we want to get an exact result, which becomes even more relevant nowadays with the explosion of the Big Data phenomenon, which makes the databases grow bigger day by day. In this work we present a parallelization for the neighbor-search algorithms included in the MLPack library, chosen as basis due to the efficiency that the implementation shows in the sequential version. The domain decomposition technique has been used in order to distribute the workload in a High Performance Computing multinode cluster and this decision has made it possible to come up with two different implementations depending on the set we choose to decompose, the query set or the reference set. MPI has been used as the message-passing interface to coordinate the parallelization among nodes. The code is available on Github1 Performance tests of both implementations have been carried out on an 8-node cluster, with 64 GB of memory and 16 cores per node (128 nodes in total) and the obtained results were very satisfactory, with speedups up to 114x.