ANN-RSFK: Busca genérica de similaridade em GPU

• Bruno Henrique Meyer UFPR
• Aurora Pozo UFPR
• Wagner M. Nunan Zola UFPR

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

Resumo

Este artigo apresenta o algoritmo ANN-RSFK, que utiliza como base o algoritmo RSFK baseado em árvores para resolver problemas de buscas de similaridades em GPU. A proposta foi comparada com estratégias presentes na biblioteca FAISS, que também utilizam GPU para executar os algoritmos. O ANN-RSFK apresentou melhor custo-benefício entre tempo e qualidade para baixos valores de acurácia, e demonstra potencial para superar as estratégias da biblioteca FAISS em diversos cenários.

Referências

Aumüller, M., Bernhardsson, E., and Faithfull, A. (2017). Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. In International Conference on Similarity Search and Applications, pages 34–49. Springer.

Johnson, J., Douze, M., and Jégou, H. (2017). Billion-scale similarity search with gpus. arXiv preprint arXiv:1702.08734.

Meyer, B., Pozo, A., and Nunan Zola, W. M. (2021a). Warp-centric k-nearest neighbor graphs construction on gpu. In 50th International Conference on Parallel Processing Workshop, pages 1–10.

Meyer, B. H., Pozo, A. T. R., and Zola, W. M. N. (2021b). Improving barnes-hut t-sne algorithm in modern gpu architectures with random forest knn and simulated wide-warp. ACM Journal on Emerging Technologies in Computing Systems (JETC), 17(4):1–26.