PARALLEL K-SET MUTUAL RANGE-JOIN IN HYPERCUBES

The mutual range-join of k sets, S-1, S-2, ... S-k, is the set contain ing all tuples (s(1), s(2), ... s(k)) that satisfy e(1) less than or e qual to \s(i) - s(j)\ less than or equal to e(2) for all 1 less than o r equal to i not equal j less than or equal to k, where s(i) is an ele ment of S-i and e(1) less than or equal to e(2) are fixed constants. T his 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 nu mbers among k given numbers are within a given range and applies the t echnique of permutation-based range-join [11]. To compute the mutual r ange-join of k sets S-1, S-2, ... S-k in a hypercube of p processors w ith O(Sigma(i=1)(k)n(i)/p) local memory, p less than or equal to \S-i\ = n(i) and 1 less than or equal to i less than or equal to k, our alg orithm requires at most O((k log k/p)Pi(i=1)(k)n(i)) data comparisons in the worst case. The algorithm is implemented in PVM and its perform ance is extensively evaluated on various input data.