Efficient database support for spatial applications

This thesis concerns efficient support of geo-spatial applications on large volumes of spatial data. This thesis examines efficient algorithms for evaluating two important spatial operations: the spatial join and the spatial aggregate. A spatial join combines two spatial data sets based on some spatial relationship between the elements in the two data sets. For example, map overlap, which requires combining two maps to produce a third, is a spatial join. A spatial aggregate summarizes the input by applying a spatial aggregate function. An example of spatial aggregation is locating the closest airport to a point on the map. Both the spatial join and the spatial aggregate operations and very expensive to compute. Consequently, efficient algorithms for both these operations are critical to the overall performance of a spatial database system. The first part of this thesis presents a new algorithm for evaluating a spatial join, and compares its performance with other spatial join algorithms. This part of the thesis also presents an algorithm for evaluating the spatial aggregate operation. This spatial aggregate algorithm uses a spatial index to speed up the evaluation. The second part of this thesis focuses on using parallelism to evaluate spatial queries. Two issues are considered here: how to decluster spatial data in a parallel database system, and how to use parallelism to efficiently evaluate spatial operations. Various spatial declustering strategies, which are based on partitioning the space in which the spatial objects lie and mapping the space partitions to nodes, are presented and evaluated. Then, based on these declustering strategies, a design space for parallel spatial join algorithms is presented. Analytical models and results from an actual implementation show that the performance of these algorithms is very sensitive to the underlying characteristics of the spatial data. Finally, this thesis presents an algorithm for evaluating the spatial aggregate operation in a parallel environment.