Abstract:  

Introduces a spatial access method, the SB+-tree, that is based on the B+-tree structure. For each axis of the space, a set of indexing points is generated; an indexing point is created whenever a new minimum bounding rectilinear rectangle (MBR) begins or ends. These indexing points are then used to create an SB+-tree. We present algorithms using an SB+-tree for performing two spatial selection operators (window intersection and point containment), and one spatial join operator (region containment). Analytically, we show the improved performance of the window intersection operation using an SB+-tree over using existing paged-secondary memory spatial access structures such as the R*-tree.