A revised r*-tree in comparison with related index structures

In this paper we present an improved redesign of the R*-tree that is entirely suitable for running within a DBMS. Most importantly, an insertion is guaranteed to be restricted to a single path because re-insertion could be abandoned. We re-engineered both, subtree choice and split algorithm, to be more robust against specific data distributions and insertion orders, as well as peculiarities often found in real multidimensional data sets. This comes along with a substantial reduction in CPU-time.