Composite Distance Transformation for Indexing and κ-Nearest-Neighbor Searching in High-Dimensional Spaces  

作　　者：庄毅 庄越挺 吴飞 

机构地区：[1]College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China

出　　处：《Journal of Computer Science & Technology》2007年第2期208-217,共10页计算机科学技术学报（英文版）

基　　金：Partially supported by the National Natural Science Foundation of China （Grant No. 60533090）, National Science Fund for Distinguished Young Scholars （Grant No. 60525108）, the National Grand Fundamental Research 973 Program of China （Grant No. 2002CB312101）, Science and Technology Project of Zhejiang Province （Grant Nos. 2005C13032, 2005C11001-05） and China-America Academic Digital Library Project （see www.cadal.zju.edu.cn）.

摘　　要：Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a ＂hard＂ problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast κ-nearest-neighbor （κ-NN） search in high-dimensional spaces. In CDT, all （n） data points are first grouped into some clusters by a κ-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B^＋-tree. Thus, given a query point, its κ-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree.Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a ＂hard＂ problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast κ-nearest-neighbor （κ-NN） search in high-dimensional spaces. In CDT, all （n） data points are first grouped into some clusters by a κ-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B^＋-tree. Thus, given a query point, its κ-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree.

关 键 词：centroid distance κ-nearest-neighbor search start distance 

分 类 号：TP393.09[自动化与计算机技术—计算机应用技术]