K-NN Search in Non-Clustered Case Using K-P-tree

摘要

Although it has been shown that all current indexing techniques degrade to linear search for sufficiently high dimensions, exact answers are still essential for many applications. A concept of "non-clustered" case is proposed in this paper. And aiming at the characteristics of such case, a new index structure named K-P-tree and a K-NN searching algorithm based on it is presented. By starting with the Self-Organized Mapping method, the partition procedure of K-P-tree does not depend on the dimensionality. Furthermore, the partition locating and pruning also benefit from the fact that only the inner borders between the partitions are recorded merely via some hyper planes. The query experiments indicate that K-P-tree outperforms many current k-NN searching approaches.