Algoritmo KNN paralelo em cluster com MPI

• Henrique L. Rieger UFPR
• Wagner M. Nunan Zola UFPR

DOI: https://doi.org/10.5753/eradrs.2023.230158

Resumo

Diversas aplicações de aprendizado de máquina e mineração de dados dependem de algoritmos bastante custosos em bases de dados de larga escala. No entanto, esses algoritmos podem obter ótimos ganhos de desempenho ao paralelizar sua operação, como é o caso do KNN (k-nearest neighbors). Neste trabalho, será apresentada uma implementação paralela em cluster do KNN, utilizando a biblioteca Open MPI e medindo seu tempo e aceleração.

Referências

Meyer, B., Pozo, A., and Nunan Zola, W. M. (2021). Warp-centric k-nearest neighbor graphs construction on GPU. In 50th International Conference on Parallel Processing Workshop, ICPP Workshops '21, New York, NY, USA. Pub. ACM.

Meyer, B., Pozo, A., and Zola, W. (2022). ANN-RSFK: Busca genérica de similaridade em GPU. In Anais da XXII Escola Regional de Alto Desempenho da Região Sul, Porto Alegre, RS, Brasil. SBC.

Shahvarani, A. and Jacobsen, H.-A. (2021). Distributed stream kNN join. In Proceedings of the 2021 International Conference on Management of Data, SIGMOD '21, page 1597-1609, New York, NY, USA. Association for Computing Machinery.

Zhang, C., Li, F., and Jestes, J. (2012). Efficient parallel kNN joins for large data in MapReduce. In Proceedings of the 15th International Conference on Extending Database Technology, New York, NY, USA. Pub. ACM.