Spatial join indices

Abstract

Algorithms based on grid files as the underlying spatial index are presented for spatial joins in databases which store images, pictures, maps and drawings. For typical data distributions, it is shown that the size of the index and its maintenance cost are relatively small. The effect of diagonal distributions and different densities of the two grid files on the size of the index is also studied. It is expected that similar algorithms can be employed with other types of multidimensional data structures.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>