Using two B + -trees to efficiently process inclusion spatial queries (extended abstract)
Mário A. Nascimento, Margaret H. Dunham · 1997
In this paper we address the problem of indexing spatial data, in particular two dimensional rectangles.We propose an approach which uses two B+-trees, each of them indexing the projected sides of the given rectangles.The approach, which we name 2dMAP21, can also be easily parallelized.We focus on queries of the type "find all rectangles included within another (reference)rectangle".We compare our approach to the R.-tree, known as the most efficient R-tree derivative.Our investigation shows that if the queries have the same spatial distribution as the data, the non-parallel 2dMAP21 may be competitive whereas the parallelized version of 2dMAP21 outperforms the R*-tree virtually always.The use of Bttrees renders our approach to be practical.