Graph Partition Based Multi-Way Spatial Joins

Free registration required

Executive Summary

In this paper, the authors investigate the problem of efficiently computing a multi-way spatial join without spatial indexes. They propose a novel and effective filtering algorithm based on a two phase partitioning technique. To avoid missing hits due to an inherent difficulty in multi-way spatial joins, they propose to firstly partition a join graph into sub-graphs whenever necessary. In the second phase, they partition the spatial data sets; and then the sub-joins will be executed simultaneously in each partition to minimise the I/O costs. Finally, a multi-way relational join will be applied to merge together the sub-join results. Their experiment results demonstrated the effectiveness and efficiency of the proposed algorithm.

  • Format: PDF
  • Size: 336.4 KB