Join-Queries between Two Spatial Datasets Indexed by a Single R*-Tree

A spatial join, a common query in Spatial Databases and Geographical Information Systems (GIS), consists in testing every possible pair of data elements belonging to two spatial datasets against a spatial predicate. This predicate might be “intersects”, “contains”, “is enclosed by”, “distance”, “northwest”, “adjacent”, “meets”, etc. The large size of datasets that appears in industrial and commercial modern applications (e.g. GIS applications, where multiple instances of the datasets are kept) raises the cost of join processing and the importance of the choice of the data indexing method and the query processing technique. The family of R-trees is considered a good choice (especially the R*-tree) for indexing a spatial dataset. When joining two datasets, a common assumption is that each dataset is indexed by a different R*-tree and the join is processed by a synchronous traversal of the two trees. In this paper, we assume that both datasets are indexed by a single R*-tree, so that spatial locality between different datasets is embedded in data indexing, facilitating the evaluation of join queries between the two datasets. We experimentally compare the I/O and Response Time performance of join queries, using this single tree indexing approach against the usual approach of indexing each dataset by a different tree.