The chain range-join of k sets, S1, S2, ? ? ?, Sk, is the set containing all tuples
(s1; s2; ? ? ? ; sk) that satisfy e(1)
i <= jsi ? si+1j <= e(2)
i , where sk 2 Sk, si 2 Si,
e(1)
i <= e(2)
i are fixed constants, 1 <= i <= k ? 1. This paper presents an efficient
parallel algorithm for computing the k-set chain range-join in hypercube computers.
The proposed algorithm applies the technique of permutation-based
range-join [10] and works by joining data sets one by one along the chain. To
compute the range-join of k sets S1, S2, ? ? ?, Sk in a hypercube of p processors,
p <= jSij = ni and 1 <= i <= k, our algorithm requires only O(?ki=1ni
p ) local memory
at each processor, and has a time complexity at most O((nkp +nk?1) log nkp )
in the best case when no element in St+1 matches any element in St for
1 <= t <= k ? 1, O(kTsort + k Qki=1 nip ) in the worst case when all elements in