Fast algorithms for spatial and multidimensional joins

grantor: University of TorontoSince the introduction of the relational model of data, the join operation has received much attention due to its unique feature of combining data from different relations. As Database Management Systems become richer in data types, there is increasing interest to extend the join operation to new data types, like geographical or spatial and multimedia data. Several algorithmic approaches have been proposed in the past. In this thesis, we present new algorithms for executing join operations between new data types. The algorithms we propose are robust, and they are generic, in the sense that they can be applied to a variety of data types. We first introduce 'Filter Trees', a new indexing structure, that supports efficient join operations between spatial data types. We introduce and define the basic operations for Filter Trees, analyzing their performance. We also propose a new algorithm for joins on spatial data types, between data sets for which no indexes are available. The algorithm is suitable for the efficient processing of intermediate query results. The new algorithm, called 'Size Separation Spatial Join', is described and analyzed. In addition we introduce a technique called, 'Dynamic Spatial Bitmaps ', which can improve the performance of Size Separation Spatial Join by allowing the algorithm to adapt to the specific data distributions in the data sets processed. Finally, we propose extensions of the Size Separation Spatial Join algorithm for data sets of higher dimensionality. The new algorithm, called ' Multidimensional Spatial Join' ('MSJ') algorithm, can efficiently perform joins between data sets containing high dimensional points. A detailed performance comparison with algorithms previously proposed is presented in each case showing the benefits of our approach.Ph.D