Data redundancy and duplicate detection in spatial join processing

The Partitioned Based Spatial-Merge Join (PBSM) of Patel and DeWitt and the Size Separation Spatial Join (S3J) of Koudas and Sevcik are considered to be among the most efficient methods for processing spa-tial (intersection) joins on two or more spatial rela-tions. Both methods do not assume the presence of pre-existing spatial indices on the relations. In this paper, we propose several improvements of these join algorithms. In particular, we deal with the impact of data redundancy and duplicate detection on the per-formance of theses methods. For PBSM, we present a simple and inexpensive on-line method to detect duplicates in the response set. There is no need any-more for eliminating duplicates in a final sorting phase as it has been suggested originally. We also investigate in this paper the impact of different inter-nal algorithms on the total runtime of PBSM. For S3J, we break with the original design goal and introduce controlled redundancy of data objects. Results of a large set of experiments with real datasets reveal that our suggested modifications of PBSM and S3J result in substantial performance improvements where PBSM is generally superior to S3J. 1