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 -