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

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

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.
Publicado
18/04/2022
MEYER, Bruno Henrique; POZO, Aurora; ZOLA, Wagner M. Nunan. ANN-RSFK: Busca genérica de similaridade em GPU. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DA REGIÃO SUL (ERAD-RS), 22. , 2022, Curitiba. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 89-90. ISSN 2595-4164. DOI: https://doi.org/10.5753/eradrs.2022.19176.