@techreport{TR-IC-97-23,
  number = {IC-97-23},
  author = {Nascimento, Mario A. and Dunham, Margaret H.},
  title = {Using {B$^+$}-Trees in a Two Disk-Single Processor Architecture to Efficiently Process Inclusion Spatial Queries},
  month = {November},
  year = {1997}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 16 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      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 using two disks --
      but still a single processor -- each holding the trees indexing
      the projected sides on either axes.  We focus on queries of the
      type ``find all rectangles included within another (reference)
      rectangle''.  Nevertheless, 2dMAP21 can processe other types of
      queries as well.  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 of the data, the non-parallel 2dMAP21 may be a
      competitive alternative to the R$^*$-tree in some cases, whereas
      the parallelized version of 2dMAP21 outperforms that structure
      virtually always.  2dMAP21 may consume a little more or less
      storage space than the R$^*$-tree, depending primarily on the
      spatial distribution on the indexed MBRs.  The use of
      B$^+$-trees renders our approach to be actually implementable
      using commercial DBMSs.
  }
}