Algorithms and optimization techniques for complex spatial queries

Spatial databases extend conventional databases to support multidimensional data. Although a number of spatial access methods and spatial join algorithms have been proposed, the efficient processing of complex spatial queries that join more than two spatial datasets, potentially restricted by spatial selections, has not been studied sufficiently.; The first contribution of this research is the proposal of Slot Index Spatial Join (SISJ), a very efficient spatial join method. SISJ matches two datasets, only one of which is indexed by an R-tree. It is based on the hash-join paradigm and utilizes the existing R-tree to determine the partition buckets. The advantages of SISJ are that it requires a single pass of the indexed data, it is robust data skew and limited memory conditions and it is co-operable with other database operators.; We integrate SISJ with other pairwise spatial join algorithms in an engine that processes multiway spatial joins, i.e. queries that match more than two spatial datasets. We provide query optimization algorithms and selectivity/cost estimation formulae. We also propose Synchronous Traversal (ST), a novel algorithm that joins more than two indexed inputs simultaneously. Experiments indicate that ST may outperform or be outperformed by combinations of pairwise join algorithms, depending on the joined inputs and query constraints. Based on these results we combine ST with pairwise join algorithms in the same engine and provide a complete solution for the problem.; Our next contribution is a study on the efficient processing of configuration similarity queries, which ask for object combinations from one or more datasets that partially or totally satisfy some spatial predicates. We show how constraint satisfaction algorithms can take advantage of indexing to accelerate search. Finally, the efficiency of local search algorithms in processing indefinite queries is studied.; Our final contribution is the extension of spatial join algorithms to process joins and selections simultaneously. We show that these hybrid methods are superior to combinations of simple selection and join operators. We also study the optimization of complex spatial queries by providing and evaluating selectivity estimation formulae for join queries that include selections.