Constraint-based processing of multiway spatial joins

A multiway spatial join combines information found in three or more spatial relations with respect to some spatial predicates. Motivated by their clos e correspondence with constraint satisfaction problems (CSPs), we show how multiway spatial joins can be processed by systematic search algorithms tra ditionally used for CSPs. This paper describes two different strategies, wi ndow reduction and synchronous traversal, that take advantage of underlying spatial indexes to prune the search space effectively. In addition, we pro vide cost models and optimization methods that combine the two strategies t o compute more efficient execution plans. Finally, we evaluate the efficien cy of the proposed techniques and the accuracy of the cost models through e xtensive experimentation with several query and data combinations.