Efficient Spatial Query Processing in Geographic Database Systems.
Hans‐Peter Kriegel, Thomas Brinkhoff, Ralf Schneider · 1993
The management of spatial data in geographic information systems (GISs) gained increasing importance during the last decade. Due to the high complexity of objects and queries and also due to extremely large data volumes, geographic database systems impose stringent requirements on their storage and access architecture with respect to efficient spatial query processing. Geographic database systems are used in very different application environments. Therefore, it is not possible to find a compact set of operations fulfilling all requirements of geographic applications. But as described in [BHKS 93], spatial selections are of great importance within the set of spatial queries and operations. They do not only represent an own query class, but also serve as a very important basis for the operations such as the nearest neighbor query and the spatial join. Therefore, an efficient implementation of spatial selections is an important requirement for good overall performance of the complete geographic database system. The two main representatives of spatial selections are the point and the window query (see figure 1): • Point query: Given a query point P and a set of objects M, the point query yields all the objects of M geometrically containing P . • Window query: Given a rectilinear rectangle W and a set of objects M, the window query yields all the objects of M sharing points with W. For the efficient processing of spatial queries, we present a multi-stepprocedure (see figure 5). The main goal of our spatial query processor is to reduce expensive steps by preprocessing operations in the preceding steps which reduce the number of objects investigated in an expensive step. In figure 5 expensive steps are marked with a “$”symbol.