Kernel based principal axis tree

K-nearest neighbors (KNN) describes a problem of finding the nearest K neighbors for a query point from a given data set. Among the available techniques, principal axis tree (PAT) always performs well when being used as an index for nearest neighbors search. As a generalization of k-dimensional tree (k-d tree), PAT uses its principal axis at each step, instead of using a coordinate axis to sort the data set. In this paper, we consider further performance improvement of PAT. Inspired by “kernel tricks” which is computationally cheaper than the explicit computation of the coordinates, we propose a kernel based principal axis tree (KPAT) method. Compared with k-d tree and PAT, the effectiveness of KPAT is verified by experimental results.