Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

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

K-NN Search in Non-Clustered Case Using K-P-Tree
View Free PDF
Author(s): Yang Zhi-rong (Sun Yat-Sen University, China)and Li Lei (Sun Yat-Sen University, China)
Copyright: 2003
Pages: 4
Source title: Information Technology & Organizations: Trends, Issues, Challenges & Solutions
Source Editor(s): Mehdi Khosrow-Pour, D.B.A. (Information Resources Management Association, USA)
DOI: 10.4018/978-1-59140-066-0.ch182
ISBN13: 9781616921248
EISBN13: 9781466665330


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.

Body Bottom