Node splitting algorithm of R*-tree based on self-adaptation clustering
-
摘要: 为提高逆向工程中点云、三角网格等数据的索引效率,提出一种R*-树结点自适应聚类分簇算法,采用均匀分布数据作为参考点集,基于间隙统计法及k-均值算法获得使结点相似度之和开始收敛的自然簇数,进而实现R*-树的结点自适应聚类分簇.实验证明,该算法可实现各类复杂几何对象的R*-树结点分簇问题,并能降低R*-树结点分簇的参数依赖性,减少结点重合度,提高R*-树空间数据查询效率.Abstract: 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.
-
Key words:
- R*-tree /
- self-adaptation clustering /
- node splitting /
- comparability value /
- gap statistic /
- k-means
-
[1] Beckmann N,Kriegel H P,Schneider R,et al.The R*-tree:an efficient and robust access method for points and rectangles[J].ACM IGMOD,1990,19(2):322-331 [2] 孙殿柱,范志先,李延瑞,等.散乱数据点云型面特征分析算法的研究与应用[J].机械工程学报,2007,43(6):133-136 Sun Dianzhu,Fan Zhixian,Li Yanrui,et al.Research and application of surface feature analysis for scatter data points[J].Chinese Journal of Mechanical Engineering,2007,43(6):133-136 (in Chinese) [3] 张明波,陆锋,申排伟,等.R树家族的演变和发展[J].计算机学报,2005,28(3):289-300 Zhang Mingbo,Lu Feng,Shen Paiwei,et al.The evolvement and progress of R-tree family[J].Chinese Journal of Computers,2005,28(3):289-300(in Chinese) [4] Brakastsoulas S,Pfoser D,Ttheodoridis Y.Revisiting R-tree construction principles[C]//Proceedings 6th ADBIS.London:Lecture Notes In Computer Science,2002:149-162 [5] Zhu Qing,Gong Jun,Zhang Yeting.An efficient 3D R-tree spatial index method for virtual geographic environments[J].ISPRS Journal of Photogrammertry and Remote Sensing,2007,62(3):217-224 [6] 黄继先,鲍光淑,夏斌.基于混合聚类算法的动态R-树[J].中南大学学报,2006,37(2):366-370 Huang Jixian,Bao Guangshu,Xia Bin.A dynamic R-tree index based on hybrid clustering algorithm[J].Journal of Central South University:Science and Technology,2006,37(2):366-370(in Chinese) [7] 孙殿柱,田中朝,李延瑞,等.基于四维聚类的R*-树结点分裂算法[J].机械工程学报,2009,45(10):180-184 Sun Dianzhu,Tian Zhongchao,Li Yanrui,et al.Node splitting algorithm of R*-tree based on four-dimensional clustering[J].Chinese Journal of Mechanical Engineering,2009,45(10):180-184(in Chinese) [8] 孙殿柱,李延瑞,朱昌志,等.几何对象统一表示的R*-tree结点分裂算法[J].华中科技大学学报,2010,38(2):55-58 Sun Dianzhu,Li Yanrui,Zhu Changzhi,et al.Node splitting algorithm for R*-tree based on united expression of all geometry objects[J].Journal of Huazhong University of Science and Technology:Nature Science,2010,38(2):55-58(in Chinese) [9] Murat Erisoglu,Nazif Calis,Sadullah Sakallioglu.A new algorithm for initial cluster centers in k-means algorithm[J].Pattern Recognition Letters,2011,32(8):1701-1705 [10] Tibshirani R,Walther G,Hastie T.Estimating the number of cluster in a dataset via the gap statistic[J].J Royal Statist Soc B,2001,32(2):411-423
点击查看大图
计量
- 文章访问数: 1582
- HTML全文浏览量: 211
- PDF下载量: 609
- 被引次数: 0