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

为提高逆向工程中点云、三角网格等数据的索引效率,提出一种R^*-树结点自适应聚类分簇算法,采用均匀分布数据作为参考点集,基于间隙统计法及k-均值算法获得使结点相似度之和开始收敛的自然簇数,进而实现R^*-树的结点自适应聚类分簇.实验证明,该算法可实现各类复杂几何对象的R^*-树结点分簇问题,并能降低R^*-树结点分簇的参数依赖性,减少结点重合度,提高R^*-树空间数据查询效率.

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

A node splitting algorithm of R^*-tree based on self-adaptation clustering was proposed to improve the spatial query efficiency of the point cloud, triangle mesh and etc. Picking some data points as reference 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. Experiment 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.