Database Systems

Multi-Step Spatial Query Processing


Multi-step spatial query processing means that queries or operations are executed in successive steps called filter- and refinement-steps. The costs of expensive operations are reduced by pre-processing steps which are more simple and efficient. The main goal of a prededing simple filter-step is to reduce the number of objects possibly fulfilling the query, so-called candidates (Ci). Candidates which do not fulfill the query are called false hits(Fi)). Only in the last step, the refinement step, an exact test is performed on the reduced set of candidates. In the figure, the cost of the processing of an object is indicated by the size of the "$"-symbol.


Important ublications in the research area 'multi-step query processing' are [Kri 91b], [BHKS 93], [KBS 93] und [BKSS 94b].Another important application area for spatial database systems are CAD-systems, which also store geometric data. Important publications in this area are [SKSH89] and [KHFM 93].

HOME Pages: DBS Institute LMU

Contact Institute: info@informatik.uni-muenchen.de
Contact WWW: wwwmaster@informatik.uni-muenchen.de