Efficient computation of spatial joins

Spatial joins are join operations that involve spatial data types and operators. Due to basic properties of spatial data, many conventional join strategies suffer serious performance penalties or are not applicable at all. The join strategies known from conventional databases that can be applied to spatial joins and the ways in which some of these techniques can be modified to be more efficient in the context of spatial data are discussed. A class of tree structures, called generalization trees, that can be applied efficiently to compute spatial joins in a hierarchical manner are described. The performances of the most promising strategies are analytically modeled and compared.>