The R*-tree: an efficient and robust access method for points and rectangles

TLDR

The R-tree, a widely used spatial index, optimizes the area of enclosing rectangles in its inner nodes, and its variants include Guttman’s linear and quadratic R-trees and Greene’s modification. The authors designed the R*-tree by optimizing area, margin, and overlap of enclosing rectangles through extensive experiments in a standardized testbed. In exhaustive tests, the R*-tree consistently outperforms existing R-tree variants across various query types, supports both points and spatial data efficiently, and incurs only a slight increase in implementation cost.

Abstract

The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R * -tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R * -tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R * -tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R * -tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.