基于均值漂移的R~＊-树结点分裂优化算法  

The Node Splitting Optimization Algorithm of R＊-tree Based on Mean Shift

作　　者：孙殿柱[1] 宋洋[1] 刘华东[1] 李延瑞[1] 

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

出　　处：《机械工程学报》2013年第13期145-149,共5页Journal of Mechanical Engineering

基　　金：国家自然科学基金(51075247);山东省自然科学基金(ZR2010EM008)资助项目

摘　　要：R*-树可有效提高散乱点云、网格曲面等数据的处理效率。为降低R*-树结点的重叠度,提高其空间利用率,将结点分裂作为模式聚类问题,采用高斯核均值漂移对结点进行模式聚类,将收敛后的模式点数量作为最佳分裂数,并以模式点为初始值结合k-均值实现R*-树的结点自适应分裂。试验证明,该算法可实现各类复杂几何对象的R*-树结点分裂问题,降低R*-树结点分裂的参数依赖性,并能有效避免k-均值的局部收敛问题,提高R*-树空间数据查询效率。The R＊-tree can improve the processing efficiency of unorganized point cloud and surface meshes. In order to reduce the overlap degree of R＊-tree nodes and increase the space utilization rate, the node splitting of R＊-tree is regarded as a pattern clustering problem, pattern clustering the nodes of R＊-tree using Gauss mean shift algorithm, the count of mode points is considered as the best splitting number, then splitting the nodes of R＊-tree with k-means algorithm whose initial values are the mode points. Experiments show that the newly proposed algorithm has good performance to solve the node splitting problems for any complex geometric object, reduce the parameter dependence, avoid the local convergence problem of k-mean effectively, and improve the R＊-tree spatial query efficiency.

关 键 词：R＊-树结点分裂 均值漂移 最优带宽 K-均值聚类 

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