基于CUK-MEANS算法的R树构建  

R Tree Construction Built Based on CUK-MEANS Algorithm

作　　者：崔环宇[1] 李松[1] 张丽平[1] 经海东 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《小型微型计算机系统》2016年第2期264-268,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61370084)资助;黑龙江省自然科学基金项目(F201302)资助;黑龙江省教育厅科学研究项目(12541128;12531z004)资助

摘　　要：针对K-means方法的不足,提出CUK-MEANS算法,用以解决K-MEANS方法在初始值选择上的不足和对噪声点敏感的问题.传统R树索引是动态生成的,通过节点的连续插入和分裂实现整个索引的构建,这种方法会造成大量的外包矩形重叠,从而导致索引效率不高.基于CUK-MEANS算法本文进一步提出了CKR-R()算法,利用聚类技术对数据进行预处理,减少节点之间的重叠度,提高了R树的索引效率,并且采用收缩因子使节点内数据更加紧凑,提高节点的空间利用率.理论研究和实验表明所提算法具有较高的查询效率.Aiming at the shortage of K-means method and in order to solve its problems of selecting the initial value and its sensitive to noise, CUK-MEANS algorithm is presented in this paper. The traditional R tree index is generated dynamically, and the construction of the whole index is realized through the continuous insertion and split of node. This method will result in overlapping of a large number of bounding rectangles, which will lead to low efficiency of the index. Based on the improved K-means method, CKR-R （ ） algorithm is put forward. The data are processed by clustering technology, which reduced the degree of overlapping between nodes and improved the efficiency of R tree index, and its adapting of the shrinkages factor makes the data within node more compact and has improved the space utilization ration of node. Theoretical research and experimental results show the query efficiency of the proposed algorithm is rather high.

关 键 词：K-MEANS算法 传统R树 索引效率 空间利用率 

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