Efficient k-nearest neighbor search based on clustering and adaptive k values. (February 2022)

• Record Type: Journal Article
• Authors: Gallego, Antonio Javier; Rico-Juan, Juan Ramón; Valero-Mas, Jose J.
• Is Part Of: Pattern recognition. Volume 122(2022)
• Publication Date: 2022-02
• Subjects: k-Nearest Neighbor -- Efficient search -- Clustering -- Feature learning; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2021.108356
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Efficient kNN search based on feature learning, clustering, and adaptive k values. Several proposals to automatically optimize the search parameters. Comprehensive experimentation with 10 datasets of different typology and size. Results demonstrate that the proposal outperforms state-of-the-art methods. Abstract: The k -Nearest Neighbor ( k NN) algorithm is widely used in the supervised learning field and, particularly, in search and classification tasks, owing to its simplicity, competitive performance, and good statistical properties. However, its inherent inefficiency prevents its use in most modern applications due to the vast amount of data that the current technological evolution generates, being thus the optimization of k NN-based search strategies of particular interest. This paper introduces the caKD+ algorithm, which tackles this limitation by combining the use of feature learning techniques, clustering methods, adaptive search parameters per cluster, and the use of pre-calculated K-Dimensional Tree structures, and results in a highly efficient search method. This proposal has been evaluated using 10 datasets and the results show that caKD+ significantly outperforms 16 state-of-the-art efficient search methods while still depicting such an accurate performance as the one by the exhaustive k NN search.