Space-Efficient Representations of Rectangle Datasets Supporting Orthogonal Range Querying

The increasing use of geographic search engines manifests the interest of Internet users in geo-located resources and, in general, in geographic infor-mation. 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 ev-ery 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 rep-resentations of rectangle datasets that can be used in the development of geographic indexes supporting orthogonal range queries