The Sort/Sweep Algorithm: A New Method for R-Tree Based Spatial Joins C. Gurret and P. Rigaux   View Paper (PDF)   Return to INDEXING Abstract We propose a new algorithm to solve the problem of joining two spatial relations R and S when S is indexed by an R-tree. The method combines classical query processing techniques and a plane-sweeping algorithm. We compare our approach to the simple indexed-nested-loop method and to the state-of-the-art algorithms, and show through analysis and experiments on synthetic and real-life datasets that our method outperforms in most cases the other ones, in both CPU and I/O. More importantly, it appears to be more robust regarding the many parameters involved in spatial query processing. Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00) DiSC'01 Copyright ©2002 ACM Inc.