R-tree Spatial Index Optimization

In order to handle spatial data more efficiently, as requested in the Digital Earth project and geo-data application on Internet, R-tree, one of the most import spatial indexes, must be more efficient. However, the previous algorithm for optimal bipartition of a rectangle set slows down the whole efficiency of R-tree.In this paper, we give a more efficient bipartition algorithm, which eliminates the inappropriate bipartitions and reduces the cost of optimal bipartition according to the character of the rectangles distribution. We present the results of series test which indicate that the new bipartition algorithm performs very well, and conclude that it can enhance the performance of the current R-tree.