GIPSY: Joining Spatial Datasets with Contrasting Density

Many scientific and geographical applications rely on the efficient execution of spatial joins. Past research has produced several efficient spatial join approaches and while each of them can join two datasets, the problem of efficiently joining two datasets with contrasting density, i.e., with the same spatial extent but with a wildly different number of spatial elements, has so far been overlooked. State-of-the-art data-oriented spatial join approaches (e.g., based on the R-Tree) suffer from degraded performance due to overlap, whereas space-oriented approaches excessively read data from disk.

In this paper we develop GIPSY, a novel approach for the spatial join of two datasets with contrasting density. GIPSY uses fine-grained data-oriented partitioning and thus only retrieves the data needed for the join. At the same time it avoids the overlap related problems associated with data-oriented partitioning by using a crawling approach, i.e., without using a hierarchical tree. Our experiments show that GIPSY outperforms state-of-the-art disk-based spatial join algorithms by a factor of 2 to 18 and is particularly efficient when joining a dense dataset with several sparse datasets.