TY - JOUR
T1 - Parallel K-set mutual range-join in hypercubes
AU - Shen, Hong
N1 - Funding Information:
” This work was partially supported by Australia Research Council under its Small Grants Scheme. ’ Email: [email protected]
PY - 1995/11
Y1 - 1995/11
N2 - The mutual range-join of k sets, S1, S2,..., Sk, is the set containing all tuples (s1, s2..., sk) that satisfy 1 ≤ |si - sj | ≤ e2 for all 1 ≤i≠j≤k, where si ε{lunate} Si and e1 ≤ e2 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 S1,S2,..., Sk in a hypercube of p processors with O(∑ki = 1nini/p) local memory, p ≤ |Si| = ni and 1 ≤ i ≤ k, our algorithm requires at most O((k log k/p)πki = 1ni) data comparisons in the worst case. The algorithm is implemented in PVM and its performance is extensively evaluated on various input data.
AB - The mutual range-join of k sets, S1, S2,..., Sk, is the set containing all tuples (s1, s2..., sk) that satisfy 1 ≤ |si - sj | ≤ e2 for all 1 ≤i≠j≤k, where si ε{lunate} Si and e1 ≤ e2 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 S1,S2,..., Sk in a hypercube of p processors with O(∑ki = 1nini/p) local memory, p ≤ |Si| = ni and 1 ≤ i ≤ k, our algorithm requires at most O((k log k/p)πki = 1ni) data comparisons in the worst case. The algorithm is implemented in PVM and its performance is extensively evaluated on various input data.
KW - Data comparison
KW - Hypercube
KW - Parallel algorithm
KW - Permutation
KW - Range-join
UR - http://www.scopus.com/inward/record.url?scp=0029403649&partnerID=8YFLogxK
U2 - 10.1016/0165-6074(95)00018-J
DO - 10.1016/0165-6074(95)00018-J
M3 - Article
AN - SCOPUS:0029403649
SN - 0165-6074
VL - 41
SP - 443
EP - 448
JO - Microprocessing and Microprogramming
JF - Microprocessing and Microprogramming
IS - 7
ER -