Since 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.

In this talk, we first present an overview of work in the area of spatial and multimedia queries. We then introduce a new algorithm to compute the spatial join of two or more spatial data sets, when indexes are not available on them. Size Separation Spatial Join (S\u3\dJ) imposes a hierarchical decomposition of the data space and, in contrast with previous approaches, requires no replication of entities from the input data sets. Thus its performance is a function of the original size of the joined data sets.

We describe S\u3\dJ and present an analytical and experimental evaluation of its I/O and processor requirements comparing them with those of previously proposed algorithms for the same problem. In addition, we introduce Dynamic Spatial Bitmaps (DSB), a new technique that enables S\u3\dJ to dynamically or statically exploit bitmap query processing techniques.

We conclude by discussing generalizations of S\u3\dJ in order to apply to other data types.