Efficient parallel k-set chain range-join in hypercubes

The chain range-join of k sets, S₁, S₂, ..., S_k, is the set containing all tuples (s₁, s₂, ..., s_k) that satisfy ei(1)≤|si-si+1|≤ei(2), where sk∈ Sk,si∈Si,ei(1)≤ei(2)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 and works by joining data sets one by one along the chain. To compute the range-join of k sets S₁, S₂, ..., S_k in a hypercube of p processors, p ≤ |S_i| = n_i and 1 ≤ i ≤ k, our algorithm requires only yO(∑i=1knip)local memory at each processor, and has a time complexity at most O(((n_k/p) + n_k-1) log(n_k/p)) in the best case when no element in S_{t + 1} matches any element in S_t, for 1≤t≤k-1,O(kTsort+(k2/pΠi=1kni))in the worst case when all elements in S_{t + 1} match each element in S_t, where Tsort=O((K/P)Πi=2knilogΠi-2kni)when all elements in S_{t + 1} are distinct, and Tsort=O((K/P)Πi=2kni)when all elements in S_{t + 1} 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.