A Decision Algorithm on Judging the Overlap of Nodes for R*Tree Based on Clustering Analysis

Clustering analysis can implement the clustering partitions for a large amount of spatial objects and optimize the nodes of the R\+*tree. The superiority of R\+*tree holds for different types of queries and operations for both rectangles and multidimensional points with effect and efficiency. Since the query efficiency of R\+*tree is mainly impacted by the factor of overlap and overlay, according to the forced reinsertion principle of the R\+*tree and based on the clustering analysis, an algorithm which applies the diagonal line segment pairs intersection is presented to judge the overlaps among the clustering nodes. The novel algorithm overcomes the existing problems of only changing the bounding form or shrinking the orthogonal bounding rectangle in solving the overlaps among nodes in most index research. With the decision algorithm, the number of iterations in clustering algorithms, can be controled, and the influence of the noise point on the clustering can be decreased. The theoretical analysis concludes that the time complexity of the algorithm is the magnitude of O(nlogn),where n is the number of the diagonal line segment pairs. Experimental results indicate that the query efficiency based on the R\+*tree, which uses the decision algorithm, outperforms that of the gain/loss-metrics-applied greedy algorithm based on the R\+*tree and the original algorithm based on SR-tree in spatial range query.