Efficient parallel k-set chain range-join in hypercubes

Hong Shen

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)217-226
Number of pages10
JournalComputer Journal
Volume38
Issue number3
DOIs
Publication statusPublished - 1995
Externally publishedYes

Fingerprint

Dive into the research topics of 'Efficient parallel k-set chain range-join in hypercubes'. Together they form a unique fingerprint.

Cite this