Efficient parallel k-set chain range-join in hypercubes

Hong Shen

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)


The chain range-join of k sets, S1, S2, ..., Sk, is the set containing all tuples (s1, s2, ..., sk) that satisfy ei(1)≤|si-si+1|≤ei(2), where sk∈ Sk,si∈Si,ei(1)≤ei(2)are fixed constants, 1 ≤ i ≤ k - 1. This paper presents an efficient parallel algorithm for computing the k-set chain range-join in hypercube computers. The proposed algorithm applies the technique of permutation-based range-join and works by joining data sets one by one along the chain. To compute the range-join of k sets S1, S2, ..., Sk in a hypercube of p processors, p ≤ |Si| = ni and 1 ≤ i ≤ k, our algorithm requires only yO(∑i=1knip)local memory at each processor, and has a time complexity at most O(((nk/p) + nk-1) log(nk/p)) in the best case when no element in St + 1 matches any element in St, for 1≤t≤k-1,O(kTsort+(k2/pΠi=1kni))in the worst case when all elements in St + 1 match each element in St, where Tsort=O((K/P)Πi=2knilogΠi-2kni)when all elements in St + 1 are distinct, and Tsort=O((K/P)Πi=2kni)when all elements in St + 1 are equal. The general-case time complexity of the algorithm is also shown. The algorithm is implemented on a UNIX-based network using a simulator designed in C and its performance is fully evaluated through extensive testing.

頁(從 - 到)217-226
期刊Computer Journal
出版狀態Published - 1995


深入研究「Efficient parallel k-set chain range-join in hypercubes」主題。共同形成了獨特的指紋。