Servers Investigate

A Non-Blocking Parallel Spatial Join Algorithm

Download now Free registration required

Executive Summary

Interest in incremental and adaptive query processing has led to the investigation of equijoin evaluation algorithms that are non-blocking. This investigation has yielded a number of algorithms, including the symmetric hash join, the XJoin, the Ripple Join, and their variants. However, to the knowledge no one has proposed a non-blocking spatial join algorithm. In this paper, the authors propose a parallel non-blocking spatial join algorithm that uses duplicate avoidance rather than duplicate elimination. Results from a prototype implementation in a commercial parallel object-relational DBMS show that it generates answer tuples steadily even in the presence of memory overflow, and that its rate of producing answer tuples scales with the number of processors.

  • Format: PDF
  • Size: 105.34 KB