Parallel K-set mutual range-join in hypercubes

The mutual range-join of k sets, S₁, S₂,..., S_k, is the set containing all tuples (s₁, s₂..., s_k) that satisfy ₁ ≤ |s_i - s_j | ≤ e₂ for all 1 ≤i≠j≤k, where s_i ε{lunate} S_i and e₁ ≤ e₂ are fixed constants. This paper presents an efficient parallel algorithm for computing the k-set mutual range-join in hypercube computers. The proposed algorithm uses a fast method to determine whether the differences of all pair numbers among k given numbers are within a given range and applies the technique of permutation-based range-join [11]. To compute the mutual range-join of k sets S₁,S₂,..., S_k in a hypercube of p processors with O(∑^k_{i = 1}n_in_i/p) local memory, p ≤ |S_i| = n_i and 1 ≤ i ≤ k, our algorithm requires at most O((k log k/p)π^k_{i = 1}n_i) data comparisons in the worst case. The algorithm is implemented in PVM and its performance is extensively evaluated on various input data.