KNN paralelo em GPU para grandes volumes de dados com agregação de consultas
Resumo
Algoritmos de aprendizado de máquina geralmente apresentam um alto custo computacional. Várias abordagens podem ser empregadas para acelerar esses algoritmos. Uma das estratégias envolve a utilização de unidades de processamento gráfico (GPU). Nesse cenário, este artigo apresenta uma implementação eficiente para processamento do algoritmo exato para consultas K-Nearest Neighbor (KNN) em GPU. O algoritmo proposto foi comparado com algoritmos disponíveis na biblioteca FAISS amplamente utilizada para busca de similaridade baseada em GPU. Experimentos demonstraram que nosso novo algoritmo para KNN exato supera o FAISS para grandes conjuntos de dados quando há apenas um ponto no conjunto de pesquisa. O novo kernel também apresenta melhores resultados com a agregação de consultas, sendo uma boa alternativa para uso em aplicações que podem realizar consultas paralelas em pequenos lotes, onde obteve aceleração de até 4.76 vezes em relação ao algoritmo exato da biblioteca FAISS, até 10.46 vezes em relação ao algoritmo aproximado.
Referências
Cordeiro, M., Meyer, B., and Zola, W. (2023). KNN exato em GPU. In Anais da XXIII Escola Regional de Alto Desempenho da Região Sul, Porto Alegre, RS, Brasil. SBC.
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. (2009). Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255.
Deng, L. (2012). The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 29(6):141–142.
Google (2013). Google Code Archive. https://code.google.com/archive/p/word2vec/. Acessado em 15/08/2023.
Gu, Y., Liu, G., Qi, J., Xu, H., Yu, G., and Zhang, R. (2017). The moving K diversified nearest neighbor query. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 31–32.
Gupta, K., Stuart, J. A., and Owens, J. D. (2012). A study of persistent threads style GPU programming for GPGPU workloads. In 2012 Innovative Parallel Computing (InPar).
Güting, R., Behr, T., and Xu, J. (2010). Efficient k-nearest neighbor search on moving object trajectories. The Vldb Journal VLDB, 19.
Iwerks, G. S., Samet, H., and Smith, K. (2003). Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the 29th International Conference on Very Large Data Bases Volume 29, VLDB ’03, page 512–523.
Johnson, J., Douze, M., and Jégou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547.
Li, J., Ni, C., He, D., Li, L., Xia, X., and Zhou, X. (2022). Efficient KNN query for moving objects on time-dependent road networks. The VLDB Journal, 32(3):575–594.
Lin, H., Shen, Z., Zhou, H., Liu, X., Zhang, L., Xiao, G., and Cheng, Z. (2020). KNN-Q learning algorithm of bitrate adaptation for video streaming over HTTP. In 2020 Information Communication Technologies Conference (ICTC), pages 302–306.
Liu, X. and Ferhatosmanoğlu, H. (2003). Efficient k-NN search on streaming data series. In Hadzilacos, T., Manolopoulos, Y., Roddick, J., and Theodoridis, Y., editors, Advances in Spatial and Temporal Databases, pages 83–101. Springer Berlin Heidelberg.
Mahesh, B. (2020). Machine learning algorithms-a review. International Journal of Science and Research (IJSR), 9(1):381–386.
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, pages 89–90, Porto Alegre, RS, Brasil. SBC.
Meyer, B. H. and Nunan Zola, W. M. (2023). Towards a GPU accelerated selective sparsity multilayer perceptron algorithm using K-nearest neighbors search. In Workshop Proceedings of the 51st International Conference on Parallel Processing, ICPP Workshops ’22, New York, NY, USA. Association for Computing Machinery.
Song, Z. and Roussopoulos, N. (2001). K-nearest neighbor search for moving query point. In Jensen, C. S., Schneider, M., Seeger, B., and Tsotras, V. J., editors, Advances in Spatial and Temporal Databases, pages 79–96. Springer Berlin Heidelberg.
Ukey, N., Yang, Z., Li, B., Zhang, G., Hu, Y., and Zhang, W. (2023). Survey on exact knn queries over high-dimensional data space. Sensors, 23(2).
Velentzas, P., Vassilakopoulos, M., and Corral, A. (2020). A partitioning gpu-based algorithm for processing the k nearest-neighbor query. In Proceedings of the 12th International Conference on Management of Digital EcoSystems, New York, NY, USA.
Yeh, M.-Y., Wu, K.-L., Yu, P., and Chen, M.-S. (2008). LeeWave: Levelwise distribution of wavelet coefficients for processing kNN queries over distributed streams. PVLDB.
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. (2009). Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255.
Deng, L. (2012). The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 29(6):141–142.
Google (2013). Google Code Archive. https://code.google.com/archive/p/word2vec/. Acessado em 15/08/2023.
Gu, Y., Liu, G., Qi, J., Xu, H., Yu, G., and Zhang, R. (2017). The moving K diversified nearest neighbor query. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 31–32.
Gupta, K., Stuart, J. A., and Owens, J. D. (2012). A study of persistent threads style GPU programming for GPGPU workloads. In 2012 Innovative Parallel Computing (InPar).
Güting, R., Behr, T., and Xu, J. (2010). Efficient k-nearest neighbor search on moving object trajectories. The Vldb Journal VLDB, 19.
Iwerks, G. S., Samet, H., and Smith, K. (2003). Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the 29th International Conference on Very Large Data Bases Volume 29, VLDB ’03, page 512–523.
Johnson, J., Douze, M., and Jégou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547.
Li, J., Ni, C., He, D., Li, L., Xia, X., and Zhou, X. (2022). Efficient KNN query for moving objects on time-dependent road networks. The VLDB Journal, 32(3):575–594.
Lin, H., Shen, Z., Zhou, H., Liu, X., Zhang, L., Xiao, G., and Cheng, Z. (2020). KNN-Q learning algorithm of bitrate adaptation for video streaming over HTTP. In 2020 Information Communication Technologies Conference (ICTC), pages 302–306.
Liu, X. and Ferhatosmanoğlu, H. (2003). Efficient k-NN search on streaming data series. In Hadzilacos, T., Manolopoulos, Y., Roddick, J., and Theodoridis, Y., editors, Advances in Spatial and Temporal Databases, pages 83–101. Springer Berlin Heidelberg.
Mahesh, B. (2020). Machine learning algorithms-a review. International Journal of Science and Research (IJSR), 9(1):381–386.
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, pages 89–90, Porto Alegre, RS, Brasil. SBC.
Meyer, B. H. and Nunan Zola, W. M. (2023). Towards a GPU accelerated selective sparsity multilayer perceptron algorithm using K-nearest neighbors search. In Workshop Proceedings of the 51st International Conference on Parallel Processing, ICPP Workshops ’22, New York, NY, USA. Association for Computing Machinery.
Song, Z. and Roussopoulos, N. (2001). K-nearest neighbor search for moving query point. In Jensen, C. S., Schneider, M., Seeger, B., and Tsotras, V. J., editors, Advances in Spatial and Temporal Databases, pages 79–96. Springer Berlin Heidelberg.
Ukey, N., Yang, Z., Li, B., Zhang, G., Hu, Y., and Zhang, W. (2023). Survey on exact knn queries over high-dimensional data space. Sensors, 23(2).
Velentzas, P., Vassilakopoulos, M., and Corral, A. (2020). A partitioning gpu-based algorithm for processing the k nearest-neighbor query. In Proceedings of the 12th International Conference on Management of Digital EcoSystems, New York, NY, USA.
Yeh, M.-Y., Wu, K.-L., Yu, P., and Chen, M.-S. (2008). LeeWave: Levelwise distribution of wavelet coefficients for processing kNN queries over distributed streams. PVLDB.
Publicado
17/10/2023
Como Citar
CORDEIRO, Michel B.; ZOLA, Wagner M. Nunan.
KNN paralelo em GPU para grandes volumes de dados com agregação de consultas. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 24. , 2023, Porto Alegre/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 253-264.
DOI: https://doi.org/10.5753/wscad.2023.235966.
