On Optimal Node Splitting for R-trees
Yván J. García, Mario Alberto Lopez, Scott T. Leutenegger · 1998
The problem of finding an optimal bipartition of a rectangle set has a direct impact on query performance of dynamic R-trees. During up-date operations, overflowed nodes need to be split (bipartitioned) with the goal of minimiz-ing resultant expected query time. The pre-vious algorithm for optimal node splitting re-quires exponential time. One contribution of this paper is a polynomial time algorithm for finding optimal bipartitions for any objective function whose value depends exclusively on the bounding hyper-rectangles of the ensuing partitions. The algorithm runs in O(nd) time where d> 1 is the number of dimensions of the input. Experimental studies indicate that the use of optimal splits alone results in im-provements of query performance of only be-tween 5 % and 15 % when compared to other heuristics. Thus, a second contribution is to demonstrate the near optimality of previous split heuristics, a fact that suggests that re-search should focus on global rather than local optimization issues. Finally, we propose a new dynamic R-tree insertion method that uses a more global restructuring heuristic when pro-cessing node overflows. When coupled with This work has been partially supported by the National Sci-