Complex spatial query processing

Abstract

The user of a Geographical Information System is not limited to conventional spatial selections and joins, but may also pose more complicated and descriptive queries. In this paper, we focus on the efficient processing and optimization of complex spatial queries that involve combinations of spatial selections and joins. Our contribution is manifold; we first provide formulae that accurately estimate the selectivity of such queries. These formulae, paired with cost models for selections and joins can be used to combine spatial operators in an optimal way. Second, we propose algorithms that process spatial joins and selections simultaneously and are typically more efficient than combinations of simple operators. Finally we study the problem of optimizing complex spatial queries using these operators, by providing (i) cost models, and (ii) rules that reduce the optimization space significantly. The accuracy of the selectivity models and the efficiency of the proposed algorithms are evaluated through experimentation. © 2004 Kluwer Academic Publishers.