Integration of Spatial Join Algorithms for Joining Multiple Inputs

Nikos Mamoulis       Dimitris Papadias*
Computer Science Dept, University of Science and Technology       Computer Science Dept, University of Science and Technology
mamoulis@cs.ust.hk       dimitris@cs.ust.hk

Abstract

Several techniques that compute the join between two spatial data sets have been proposed during the last decade. Among these methods, some consider existing indices for the joined inputs, while others treat datasets with no index, thus providing solutions for the case where at least one input comes as an intermediate result of another database operator. In this paper we analyse previous work on spatial joins and propose a novel algorithm, called slot index spatial join (SISJ), that efficiently computes the spatial join between two inputs, only one of which is indexed by an R-tree. Going one step further, we show how SISJ and other spatial join algorithms can be implemented as operators in a database environment that joins more than two spatial inputs. We study the differences between relational and spatial multi-way joins and propose a dynamic programming algorithm that optimizes the execution of complex spatial queries.