Space-Efficient Representations of Rectangle Datasets Supporting Orthogonal
Range Querying
Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco
The increasing use of geographic search engines manifests the interest of
Internet users in geo-located resources and, in general, in geographic
information. This has
emphasized the importance of the development of efficient indexes over large
geographic databases. The most common simplification of geographic objects
used for indexing
purposes is a two-dimensional rectangle. Furthermore, one of the
primitive operations that must be supported by every
geographic index structure is the orthogonal range query, which
retrieves all the geographic objects that have at least one point in common
with a rectangular
query region. In this work, we study several space-efficient representations
of rectangle datasets that
can be used in the development of geographic indexes supporting orthogonal
range queries.