Fast exact pairwise-nearest-neighbor algorithm using groups and clusters rejection criteria

Pairwise-nearest-neighbor (PNN) is an effective method of data clustering, which can usually generate good clustering results, but with high computational complexity. In this paper, a new method is presented to reduce the computational complexity of the PNN algorithm through dividing clusters into groups of clusters and using projections of clusters on differential vectors of group pairs to reject impossible groups and clusters in the nearest neighbor finding process of a cluster. Experimental results show that the proposed algorithm can effectively reduce the computing time and number of distance calculations of the PNN algorithm for data sets from real images. It is noted that the proposed method generates the same clustering results as those produced using the PNN algorithm.