IB-CBB: an improved spatial index considering intersection based on clipped bounding boxes

Abstract

ABSTRACTEfficiently querying multiple spatial datasets is a challenging task in geoscience. The majority of spatial processing techniques use minimum bounding box (MBB) to approximate neighbouring spatial objects and and place them adjacent in the spatial index. However, due to the existence of redundant space in MBB of these methods, this problem can significantly reduce the query efficiency. In this paper, we propose a novel two-stage adaptive method of clipping the bounding box in spatial query, called IB-CBB (Intersection Based Clipped Bounding Boxes). The first stage employs a clipped bounding box, which records the redundant spatial spaces within the bounding box of the spatial index by calculating the clip points. As a result, the computational complexity of indexed child nodes in the query process is reduced. The second stage optimizes the above query algorithm by judging the intersection of the query box and the MBB of index node, significantly reducing the query time. Experiments demonstrate that IB-CBB outperforms the baseline method in terms of reducing the computational time.

Keywords

• Spatial index
• minimum bounding box
• dead space
• R-tree