TY - GEN
T1 - An improved selection-based parallel range-join algorithm in hypercubes
AU - Shen, Hong
PY - 1994
Y1 - 1994
N2 - The range-join of two sets R and S is the set that contains all tuples (r, s) satisfying e1 ≤|r - s| ≤e2, r ε R and s ε S. For computing the range-join of R and S in a hypercube of p processors, this paper presents an improved selection-based parallel algorithm which reduces the local memory from O(n) required in the previous algorithm [10] to Q(m+n/p), where |R| = m, |S| - n and p ≤ max{m, n}. The new algorithm also reduces the best-case time complexity from 0( m/p log2 p+n/p logm) of the previous result to 0(m+n/p log2p) when m ≥ plogP, while maintaining the cost optimality in the worst case. Unlike the previous algorithm, our algorithm works by selecting the median of R U S to evenly partition the whole data set for divide-and-conquer join in the next phase. We present an upper bound of time complexity of the algorithm in the general case and show that the best-case time complexity of the algorithm is better than permutation-based range-join [9] when n ≥ plogp+1.
AB - The range-join of two sets R and S is the set that contains all tuples (r, s) satisfying e1 ≤|r - s| ≤e2, r ε R and s ε S. For computing the range-join of R and S in a hypercube of p processors, this paper presents an improved selection-based parallel algorithm which reduces the local memory from O(n) required in the previous algorithm [10] to Q(m+n/p), where |R| = m, |S| - n and p ≤ max{m, n}. The new algorithm also reduces the best-case time complexity from 0( m/p log2 p+n/p logm) of the previous result to 0(m+n/p log2p) when m ≥ plogP, while maintaining the cost optimality in the worst case. Unlike the previous algorithm, our algorithm works by selecting the median of R U S to evenly partition the whole data set for divide-and-conquer join in the next phase. We present an upper bound of time complexity of the algorithm in the general case and show that the best-case time complexity of the algorithm is better than permutation-based range-join [9] when n ≥ plogp+1.
UR - http://www.scopus.com/inward/record.url?scp=0006114238&partnerID=8YFLogxK
U2 - 10.1109/EURMIC.1994.390405
DO - 10.1109/EURMIC.1994.390405
M3 - Conference contribution
AN - SCOPUS:0006114238
SN - 0818664304
SN - 9780818664304
T3 - Conference Proceedings of the EUROMICRO
SP - 65
EP - 72
BT - Proceedings of the 20th EUROMICRO Conference on System Architecture and Integration, EUROMICRO 1994
PB - IEEE Computer Society
T2 - 20th EUROMICRO Conference on System Architecture and Integration, EUROMICRO 1994
Y2 - 8 September 1994 through 8 September 1994
ER -