Comparison of scalable distributed algorithms for assessing the kNNG in multi-GPU

• Gabriel Orlando UFSCar
• Hermes Senger UFSCar
• Murilo Naldi UFSCar

DOI: https://doi.org/10.5753/wscad.2023.235822

Resumo

Many applications, require finding a dataset’s k-Nearest Neighbors Graph (kNNG), crucial for many Machine Learning tasks like clustering and anomaly detection. However, its computation can be costly due to the complexity of finding all kNN for every data point. To address this issue, scalable approximated algorithms have been proposed to speed up the kNNG and maintain its quality. This paper presents an adaption of NNDescent using multi-GPU and an experimental comparison of distributed and parallel approximate kNNG algorithms in GPUs, assessing their scalability, computational cost, and solution quality. Our goal is to identify the most efficient method without significant accuracy loss, enabling faster techniques and handling large datasets.

Referências

Amato, G. and Savino, P. (2010). Approximate similarity search in metric spaces using inverted files. In Proceedings of the 3rd International ICST Conference on Scalable Information Systems. ICST.

Andrade, G., Ramos, G., Madeira, D., Sachetto, R., Ferreira, R., and Rocha, L. (2013). G-dbscan: A gpu accelerated algorithm for density-based clustering. Procedia Computer Science, 18:369–378. 2013 International Conference on Computational Science.

Asano, S., Maruyama, T., and Yamaguchi, Y. (2009). Performance comparison of fpga, gpu and cpu in image processing. In 2009 international conference on field programmable logic and applications, pages 126–131. IEEE.

Croix, J. F. and Khatri, S. P. (2009). Introduction to gpu programming for eda. In Proceedings of the 2009 International Conference on Computer-Aided Design, pages 276–280.

Dhillon, I. S. (2001). Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01, page 269–274, New York, NY, USA. Association for Computing Machinery.

Dong, W., Charikar, M., and Li, K. (2011). Efficient k-nearest neighbor graph construction for generic similarity measures. In Srinivasan, S., Ramamritham, K., Kumar, A., Ravindra, M. P., Bertino, E., and Kumar, R., editors, Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 April 1, 2011, pages 577–586. ACM.

Fogal, T., Childs, H., Shankar, S., Krüger, J. H., Bergeron, R. D., and Hatcher, P. J. (2010). Large data visualization on distributed memory multi-gpu clusters. High Performance Graphics, 3:57–66.

Jogalekar, P. and Woodside, M. (2000). Evaluating the scalability of distributed systems. IEEE Transactions on parallel and distributed systems, 11(6):589–603.

Johnson, J., Douze, M., and Jégou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547.

Jégou, H., Douze, M., and Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128.

Kang, B., Kim, D., and Kang, S. (2012). Real-time business process monitoring method for prediction of abnormal termination using knni-based LOF prediction. Expert Syst. Appl., 39(5):6061–6068.

Kuttranont, P., Boonprakob, K., Phaudphut, C., Permpol, S., Aimtongkhamand, P., KoKaew, U., Waikham, B., and So-In, C. (2017). Parallel knn and neighborhood classification implementations on gpu for network intrusion detection. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(22):29–33.

Patel, Y., Tolias, G., and Matas, J. (2022). Recall@ k surrogate loss with large batches and similarity mixup. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7502–7511.

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830.

Pereira, F., Theis, C., Moreira, A. J. C., and Ricardo, M. (2012). Performance and limits of knn-based positioning methods for GSM networks over leaky feeder in underground tunnels. J. Locat. Based Serv., 6(2):117–133.

Shimomura, L. C., Oyamada, R. S., Vieira, M. R., and Kaster, D. S. (2021). A survey on graph-based methods for similarity searches in metric spaces. Information Systems, 95:101507.

Spampinato, D. G., Elster, A. C., and Natvig, T. (2010). Modelling multi-gpu systems. In Parallel Computing: From Multicores and GPU’s to Petascale, pages 562–569. Ios Press.

Turan, H. H., Sleptchenko, A., Pokharel, S., and ElMekkawy, T. Y. (2020). A sorting based efficient heuristic for pooled repair shop designs. Comput. Oper. Res., 117:104887.

Wang, H., Zhao, W., Zeng, X., and Yang, J. (2021a). Fast k-nn graph construction by GPU based nn-descent. In Demartini, G., Zuccon, G., Culpepper, J. S., Huang, Z., and Tong, H., editors, CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 5, 2021, pages 1929–1938. ACM.

Wang, H., Zhao, W.-L., Zeng, X., and Yang, J. (2021b). Fast k-nn graph construction by gpu based nn-descent. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1929–1938.

Wang, X., Qiu, Y., Slattery, S. R., Fang, Y., Li, M., Zhu, S.-C., Zhu, Y., Tang, M., Manocha, D., and Jiang, C. (2020). A massively parallel and scalable multi-gpu material point method. ACM Trans. Graph., 39(4).

Wang, Z. and Liu, Z. (2010). Graph-based KNN text classification. In Li, M., Liang, Q., Wang, L., and Song, Y., editors, Seventh International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2010, 10-12 August 2010, Yantai, Shandong, China, pages 2363–2366. IEEE.

Xia, J., Zhang, J., Wang, Y., Han, L., and Yan, H. (2022). WC-KNNG-PC: watershed clustering based on k-nearest-neighbor graph and pauta criterion. Pattern Recognit., 121:108177.

Xing, W. and Bei, Y. (2020). Medical health big data classification based on KNN classification algorithm. IEEE Access, 8:28808–28819.

Zhang, Y., Huang, K., Geng, G., and Liu, C. (2013). Fast knn graph construction with locality sensitive hashing. In Procedings of Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2013, Prague, Czech Republic, 2013, volume 8189 of Lecture Notes in Computer Science, pages 660–674. Springer.

Zhou, W., Lu, Y., Li, H., and Tian, Q. (2012). Scalar quantization for large scale image search. In Proceedings of the 20th ACM international conference on Multimedia, pages 169–178.