Bitmap R-trees

Abstract

Bitmap R-tree is a variant of R-tree in which bitmaps are used for the description of the internal and the external regions of the objects in addition to the use of minimum bounding rectangles. The proposed scheme increases the chance of trivial acceptance and rejection of data objects, and reduces unnecessary disk accesses in query processing. It has been shown that with the bitmaps as filters, the reference to the object data file can be cut down by as much as 60%.