R＊-树结点自适应聚类分簇算法  

Node splitting algorithm of R＊-tree based on self-adaptation clustering

作　　者：孙殿柱[1] 孙永伟[1] 李延瑞[1] 宋洋[1] 

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

出　　处：《北京航空航天大学学报》2013年第3期344-348,共5页Journal of Beijing University of Aeronautics and Astronautics

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

摘　　要：为提高逆向工程中点云、三角网格等数据的索引效率,提出一种R*-树结点自适应聚类分簇算法,采用均匀分布数据作为参考点集,基于间隙统计法及k-均值算法获得使结点相似度之和开始收敛的自然簇数,进而实现R*-树的结点自适应聚类分簇.实验证明,该算法可实现各类复杂几何对象的R*-树结点分簇问题,并能降低R*-树结点分簇的参数依赖性,减少结点重合度,提高R*-树空间数据查询效率.A node splitting algorithm of R＊ -tree based on self-adaptation clustering was proposed to im- prove the spatial query efficiency of the point cloud, triangle mesh and etc. Picking some data points as refer- ence point set with uniform sampling. The true number of clusters, which made the totality comparability value of nodes to become convergence, was obtained based on the Gap statistical method and k-means algorithm. According to the true number of clusters, the node of R＊ -tree was split without human intervention. Experi- ment results prove that the algorithm can solve the node clustering problems for any complex geometric object, reduce the parameters dependence and nodes＇ coincidence degree of node splitting of R＊-tree, and improve the R ＊-tree spatial query efficiency.

关 键 词：R＊-树 自适应聚类 结点分簇 结点相似度 间隙统计法 K-均值 

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