Abstract.
A multiway spatial join combines information found in three or more spatial relations with respect to some spatial predicates. Motivated by their close correspondence with constraint satisfaction problems (CSPs), we show how multiway spatial joins can be processed by systematic search algorithms traditionally used for CSPs. This paper describes two different strategies, window reduction and synchronous traversal, that take advantage of underlying spatial indexes to prune the search space effectively. In addition, we provide cost models and optimization methods that combine the two strategies to compute more efficient execution plans. Finally, we evaluate the efficiency of the proposed techniques and the accuracy of the cost models through extensive experimentation with several query and data combinations.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received December 21, 1998; revised September 29, 1998.
Rights and permissions
About this article
Cite this article
Papadias, D., Mamoulis, N. & Theodoridis, Y. Constraint-Based Processing of Multiway Spatial Joins . Algorithmica 30, 188–215 (2001). https://doi.org/10.1007/s00453-001-0005-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-001-0005-y