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.
Brakastsoulas S,Pfoser D,Ttheodoridis Y.Revisiting R-tree construction principles[C]//Proceedings 6th ADBIS.London:Lecture Notes In Computer Science,2002:149-162
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
黄继先,鲍光淑,夏斌.基于混合聚类算法的动态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)
孙殿柱,田中朝,李延瑞,等.基于四维聚类的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)
孙殿柱,李延瑞,朱昌志,等.几何对象统一表示的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)
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
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