Fast k-nearest neighbors search using modified principal axis search tree |
| |
Authors: | Yi-Ching Liaw Chien-Min Wu Maw-Lin Leou |
| |
Affiliation: | Department of Computer Science and Information Engineering, Nanhua University, Chiayi, 622 Taiwan, ROC |
| |
Abstract: | The problem of k-nearest neighbors (kNN) is to find the nearest k neighbors for a query point from a given data set. Among available methods, the principal axis search tree (PAT) algorithm always has good performance on finding nearest k neighbors using the PAT structure and a node elimination criterion. In this paper, a novel kNN search algorithm is proposed. The proposed algorithm stores projection values for all data points in leaf nodes. If a leaf node in the PAT cannot be rejected by the node elimination criterion, data points in the leaf node are further checked using their pre-stored projection values to reject more impossible data points. Experimental results show that the proposed method can effectively reduce the number of distance calculations and computation time for the PAT algorithm, especially for the data set with a large dimension or for a search tree with large number of data points in a leaf node. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|