Parallel Approaches for SNN-Based Nearest Neighbor Search in High-Dimensional Embedding Spaces: Application to Face Recognition
Source abstract
Abstract
The rapid growth of high-dimensional biometric data requires fast and accurate similarity search methods for real-time applications. This study proposes, for the first time, two efficient parallel implementations of the exact Sorting-based Nearest Neighbor (SNN) algorithm using OpenMP for CPUs and CUDA for GPUs. Comparative evaluation against conventional exact search methods—k-d tree and ball tree—on LFW embeddings, including FaceNet512 and VGG-Face, demonstrates an up to 58× speedup on GPUs while maintaining full accuracy. Analysis of the full recognition pipeline shows that parallelization reduces search times to about 27% of total processing, highlighting the method’s stability and efficiency for modern embeddings. These results confirm the applicability of the proposed approaches for real-time biometric identification, with potential extensions to streaming data, hybrid computing environments, and other high-dimensional representations.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Face and Expression Recognition · Advanced Image and Video Retrieval Techniques · Image Retrieval and Classification Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Artificial Intelligence, Lviv Polytechnic National University, 79013 Lviv, Ukraine
References (40)
Show source-provided references
1. Integration of Artificial Intelligence in Facial Recognition Systems for Software Security10.33395/sinkron.v8i2.13612 ↗
2. Advancements and Challenges in Face Recognition Technology10.14445/22312803/IJCTT-V72I11P110 ↗
3. R, V.C., Asha, V., Saju, B., Suma, N., Reddy, T.R.M., and Sumanth, M.K. (2023, January 5). Face Recognition and Identification Using Deep Learning. Proceedings of the 2023 Third International Conference on Advances in Electrical, Computing, Communication and Sustainable Technologies (ICAECT), Bhilai, India.10.1109/ICAECT57570.2023.10118154 ↗
4. Deng, N., Xu, Z., Li, X., Gao, C., and Wang, X. (2024). Deep Learning and Face Recognition: Face Recognition Approach Based on the DS-CDCN Algorithm. Appl. Sci., 14.10.3390/app14135739 ↗
5. Face Recognition Model Based on Deep Learning Method
6. A Benchmark of Facial Recognition Pipelines and Co-Usability Performances of Modules10.17671/gazibtd.1399077 ↗
7. Li, Z., Li, Z., and Li, X. (2025). Facial Recognition Leveraging Generative Adversarial Networks. arXiv.
8. Ding, H., Wu, J., Zhao, W., Matinlinna, J.P., Burrow, M.F., and Tsoi, J.K.H. (2023). Artificial Intelligence in Dentistry—A Review. Front. Dent. Med., 4.10.3389/fdmed.2023.1085251 ↗
9. Chen, Z., Zhang, R., Zhao, X., Cheng, X., and Zhou, X. (2025). Exploring the Meaningfulness of Nearest Neighbor Search in High-Dimensional Space. Lecture Notes in Computer Science, Springer Nature Singapore.10.1007/978-981-96-1242-0_14 ↗
10. Fast and Exact Fixed-Radius Neighbor Search Based on Sorting10.7717/peerj-cs.1929 ↗
11. Yang, S., Xie, J., Liu, Y., Yu, J.X., Gao, X., Wang, Q., Peng, Y., and Cui, J. (2024). Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search. arXiv.10.14778/3725688.3725709 ↗
12. Chen, P., Chang, W.-C., Jiang, J.-Y., Yu, H.-F., Dhillon, I., and Hsieh, C.-J. (2023, January 30). FINGER: Fast Inference for Graph-Based Approximate Nearest Neighbor Search. Proceedings of the ACM Web Conference 2023, Austin, TX, USA.10.1145/3543507.3583318 ↗
13. Medical Image Retrieval via Nearest Neighbor Search on Pre-Trained Image Features10.1016/j.knosys.2023.110907 ↗
14. Aghazadeh, A., and Amirmazlaghani, M. (2020). A Distributed Approximate Nearest Neighbor Method for Real-Time Face Recognition. arXiv.
15. Deep Learning for Approximate Nearest Neighbour Search: A Survey and Future Directions10.1109/TKDE.2022.3220683 ↗
16. Schroff, F., Kalenichenko, D., and Philbin, J. (2015, January 7–12). FaceNet: A Unified Embedding for Face Recognition and Clustering. Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA.10.1109/CVPR.2015.7298682 ↗
17. Parkhi, O.M., Vedaldi, A., and Zisserman, A. (2015, January 7–10). Deep Face Recognition. Proceedings of the British Machine Vision Conference 2015, Swansea, UK.10.5244/C.29.41 ↗
18. Nielsen, B.M.G., and Hansen, L.K. (2023). Hubness Reduction Improves Sentence-BERT Semantic Spaces. arXiv.
19. Parallel Algorithms for Nearest Neighbor Search Problems in High Dimensions10.1137/15M1026377 ↗
20. Renga Bashyam, K.G., and Vadhiyar, S. (2020, January 13). Fast Scalable Approximate Nearest Neighbor Search for High-Dimensional Data. Proceedings of the 2020 IEEE International Conference on Cluster Computing (CLUSTER), Kobe, Japan.10.1109/CLUSTER49012.2020.00040 ↗
21. LeaFi: Data Series Indexes on Steroids with Learned Filters
22. Zhao, Y., and Zhang, J. (2023, January 23). Research on Knn Algorithm Based on Kmeans Clustering and Collaborative Filtering Hybrid Algorithm in AI Teaching. Proceedings of the 2023 8th International Conference on Information Systems Engineering (ICISE), Dalian, China.10.1109/ICISE60366.2023.00102 ↗
23. Zhong, X., Li, H., Jin, J., Yang, M., Chu, D., Wang, X., Shen, Z., Jia, W., Gu, G., and Xie, Y. (2025). VSAG: An Optimized Search Framework for Graph-Based Approximate Nearest Neighbor Search. arXiv.10.14778/3750601.3750624 ↗
24. Luo, J., Zhang, M., Chen, K., Liao, X., Shan, Y., Jiang, J., and Wu, Y. (2025). Efficient Graph-Based Approximate Nearest Neighbor Search Achieving: Low Latency Without Throughput Loss. arXiv.
25. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph10.14778/3303753.3303754 ↗
26. Yang, M., Li, W., and Wang, W. (2024). Fast High-Dimensional Approximate Nearest Neighbor Search with Efficient Index Time and Space. arXiv.
27. Wang, Z., Xiong, H., Wang, Q., He, Z., Wang, P., Palpanas, T., and Wang, W. (2024). Dimensionality-Reduction Techniques for Approximate Nearest Neighbor Search: A Survey and Evaluation. arXiv.
28. Parallel Optimization of Dimensionality Reduction Methods for Disease Prediction: PCA and LDA with Dask-ML
29. Exploring the Role of Dimensionality Reduction in Enhancing Machine Learning Algorithm Performance10.9734/ajrcos/2024/v17i5445 ↗
30. Zemouri, R., Levesque, M., Boucher, E., Kirouac, M., Lafleur, F., Bernier, S., and Merkhouf, A. (2022, January 22). Recent Research and Applications in Variational Autoencoders for Industrial Prognosis and Health Management: A Survey. Proceedings of the 2022 Prognostics and Health Management Conference (PHM-2022 London), London, UK.10.1109/PHM2022-London52454.2022.00042 ↗
31. Khan, S., Singh, S., Simhadri, H.V., and Vedurada, J. (2025). BANG: Billion-Scale Approximate Nearest Neighbor Search Using a Single GPU. arXiv.
32. El Fadel, N. (2025). Facial Recognition Algorithms: A Systematic Literature Review. J. Imaging, 11.10.3390/jimaging11020058 ↗
33. Parallelization of Cryptographic Algorithm Based on Different Parallel Computing Technologies
34. Dobson, M., and Blelloch, G. (2021). Parallel Nearest Neighbors in Low Dimensions with Batch Updates. arXiv.10.1137/1.9781611977042.16 ↗
35. A Parallel Implementation of the K Nearest Neighbours Classifier in Three Levels: Threads, MPI Processes and the Grid10.1007/978-3-540-71351-7_18 ↗
36. Li, Y., Zhou, B., Zhang, J., Wei, X., Li, Y., and Chen, Y. (2024, January 30). RadiK: Scalable and Optimized GPU-Parallel Radix Top-K Selection. Proceedings of the 38th ACM International Conference on Supercomputing, Kyoto, Japan.10.1145/3650200.3656596 ↗
37. Learned-Miller, Learning to Align from Scratch
38. YuNet: A Tiny Millisecond-Level Face Detector10.1007/s11633-023-1423-y ↗
39. Sinha Face Recognition Using Transfer Learning by Deep VGG16 Model
40. A Light CNN for Deep Face Representation with Noisy Labels10.1109/TIFS.2018.2833032 ↗