Efficient Parallel k-Set Chain Range-Join in Hypercubes

The chain range-join of k sets, St,S2, ,Sk, is the set containing all tuples (st,S2, ,s*) that satisfy «,•'' ) local memory at each processor, and has a time complexity at most O(((nk/p) + nk_i)log(nk/p)) in the best case when no element in Sl+i matches any element in S, for 1 ^ t < k — 1, O(kTsort + (k 2 /p) n?=i";) m tn e worst case when all elements in Sl+i match each element in S,, where Tson = #((£//') 11?= 2 n il°gn?= 2"i) when all elements in S,+ 1 are distinct, and Tson = O((k/p) n?=2"i) when all elements in S,+i are equal. The general-case time complexity of the algorithm is also shown. The algorithm is implemented on a UNIX-based network using a simulator designed in C and its performance is fully evaluated through extensive testing.