基于最小生成树的R^＊-树结点分裂算法  

Node Splitting Algorithm of R^＊-Tree Based on Minimum Spanning Tree

作　　者：孙殿柱[1] 孙永伟[1] 康新才[1] 史阳[1] 

机构地区：[1]山东理工大学机械工程学院,山东淄博255049

出　　处：《西安交通大学学报》2011年第5期127-130,共4页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(51075247)

摘　　要：针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.Aiming at the problems of R＊-tree for reverse engineering of weak application,a new node splitting algorithm of R＊-tree is proposed.The nodes of R＊-tree are all expressed as their minimum bounding boxes.Then,the node comparability value is weighed with circum-sphere of the minimum bounding boxes.The minimum spanning tree is constructed based on the connected undirected graph of node comparability value,and the minimum spanning tree is divided into two sub-trees on the edge of the maximum weight,which gets effective for optimizing the structure of R＊-tree and improving the efficiency of node splitting.

关 键 词：逆向工程 R＊-树 轴向包围盒 结点相似度 最小生成树 

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