EVALUATION OF FAST K-NEAREST NEIGHBORS SEARCH METHODS USING REAL DATA SETS

摘要

The problem of k-nearest neighbors (kNN) search is to find nearest k neighbors from a given data set for a query point. To speed up the finding process of nearest k neighbors, many fast kNN search algorithms were proposed. The performance of fast kNN search algorithms is highly influenced by the number of dimensions, number of data points, and data distribution of a data set. In the extreme case, the performance of a fast kNN search algorithm may be poorer than the full search algorithm. To help understand the performance of fast kNN search algorithms on data sets of different types, five fast algorithms were tested in this paper using multiple real data sets. The experimental results of the paper will be very useful in choosing a fast kNN search algorithm for an unknown data set.