| The SB{dollar}sp+{dollar}-tree is an extension of the B{dollar}sp+{dollar}-tree for spatial databases. It can be used to index zero and non-zero size objects. Non-zero size objects are approximated by their minimum bounding rectangles (MBRs). The motivation behind this research is that such a structure will allow commercial databases an access method for spatial objects without a major change, since most commercial databases already support B{dollar}sp+{dollar}-tree as an access method for text data. SB{dollar}sp+{dollar}-tree is a hybrid of the existing spatial access methods. For each axis of the space, a set of indexing points is generated, where an indexing point is created whenever a new minimum bounding rectilinear rectangle (or MBR) begins or ends. The indexing points are then used to create an SB{dollar}sp+{dollar}-tree. The number of SB{dollar}sp+{dollar}-trees generated is dependent upon the number of dimensions of the approximation of the object, and not on the number of relations.; We present formal definitions for the following spatial selection and join operators: Point-Containment, Window-Intersection, Regions-Overlap, Regions-Containment, Distance and Direction. Efficient algorithms for conducting these operations using the SB{dollar}sp+{dollar}-tree are provided. The SB{dollar}sp+{dollar}-tree guarantees that one search path is required for query processing. We also present a cost model for selection and join operations using SB{dollar}sp+{dollar}-tree. Extensive experiments are presented and compared to our estimated cost. Through simulation and analysis, we show that the response time of spatial join and selection operations using SB{dollar}sp+{dollar}-tree is better compared to that of R-tree. |
