Abstract: R-tree is suitable for maintaining dynamic data and spatial query in many areas such as reverse engineering, CAD/CAM and machine vision, while CR-tree is an excellent variant of R-tree. Aiming at the deficiency in clustering result and compute cost for overflow nodes splitting algorithm of CR-tree, an incremental k-means algorithm via principal components analysis (PCA) is proposed, which can search the new cluster center along the first principal component directions in present clusters. Combining with Silhouette indicator, the algorithm is applied to solving the problem of point set clustering, which is converted from the problem of overflow nodes Splittin. Consequently the clustering results nearly global optimal can be obtained quickly. The experimental results show that the R-tree built with the algorithm based on incremental clustering is better than CR-tree and RR*-tree in synthetic performance in aspects such as the efficiency of building R-tree, storage utilization and spatial query.

Key words: dynamic spatial index, incremental k-means, overflow nodes splitting, principal components analysis, R-tree