基于CURE聚类算法的静态R树构建方法  

Static R-tree Building Method Based on Cure Clustering Algorithm

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

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

出　　处：《计算机科学》2015年第10期193-197,共5页Computer Science

基　　金：黑龙江省教育厅科学研究项目(12541128)资助

摘　　要：R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。The R tree index structure plays a great role in spatial objects query and complex spatial relations query. The traditional spatial index structure of R tree is generated dynamically. The structure of its tree is realized according to the continuous insertion algorithm. It uses the way of splitting child node to generate the root node of R tree. Dynamic gene- ration algorithm will cause low minimum utilization rate of the node of R tree. In order to make up for the inadequacy of dynamically generated R tree,a static R tree algorithm based on CURE algorithm was proposed, and the CU RHbuilt tree building method was put forward. This algorithm can not only effectively deal with massive data, recognize clusters of any shape, reduce the overlap degree of rectangles, but also greatly reduce the computational cost as partitioning tech- nology is adopted. The spatial utilization is rather high. The R tree node splitting method based on CURE algorithm was further proposed. Theoretical research and experiment show that the query efficiency of the proposed method is rather high.

关 键 词：传统R树 静态R树 CURE算法 海量数据 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]