The range-join of sets R and S is defined to be the set containing all tuples
(r; s) that satisfy e1 <= jr ? sj <= e2, where r 2 R, s 2 S, e1 and e2 are fixed
constants. This paper proposes an efficient parallel range-join algorithm in
hypercubes. To compute the range-join of two sets R and S on a hypercube of
p processors (p <= jRj = m <= jSj = n), the proposed algorithm simply permutes
the elements of R to obtain their possible combinations with the elements S and
thus all possible local range-joins. Requiring only O(m+n
p ) local memory at each
processor, our algorithm has a time complexity O((np + m) log np ) in the best
case when no element in S matches any element in R; O(T ksort + mnp ) in the worst
case when all elements in S match each element in R, where T ksort = O(k log k)
when all elements in S are distinct, and T ksort = O(k) when all elements in S
are equal, k = np . The general-case time complexity of the algorithm is also
shown.