Abstract: The R*-tree can improve the processing efficiency of unorganized point cloud and surface meshes. In order to reduce the overlap degree of R*-tree nodes and increase the space utilization rate, the node splitting of R*-tree is regarded as a pattern clustering problem, pattern clustering the nodes of R*-tree using Gauss mean shift algorithm, the count of mode points is considered as the best splitting number, then splitting the nodes of R*-tree with k-means algorithm whose initial values are the mode points. Experiments show that the newly proposed algorithm has good performance to solve the node splitting problems for any complex geometric object, reduce the parameter dependence, avoid the local convergence problem of k-mean effectively, and improve the R*-tree spatial query efficiency.

Key words: k-means clustering, Mean shift, Node splitting of R*-tree, Optimal bandwidth, finite element, infinite domain, sound radiation, wave envelope element