## Abstract

The chain range-join of k sets, S_{1}, S_{2}, ..., S_{k}, is the set containing all tuples (s_{1}, s_{2}, ..., s_{k}) 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 S_{1}, S_{2}, ..., S_{k} in a hypercube of p processors, p ≤ |S_{i}| = n_{i} and 1 ≤ i ≤ k, our algorithm requires only yO(∑i=1knip)local memory at each processor, and has a time complexity at most O(((n_{k}/p) + n_{k-1}) log(n_{k}/p)) in the best case when no element in S_{t + 1} matches any element in S_{t}, for 1≤t≤k-1,O(kTsort+(k2/pΠi=1kni))in the worst case when all elements in S_{t + 1} match each element in S_{t}, where Tsort=O((K/P)Πi=2knilogΠi-2kni)when all elements in S_{t + 1} are distinct, and Tsort=O((K/P)Πi=2kni)when all elements in S_{t + 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 language | English |
---|---|

Pages (from-to) | 217-226 |

Number of pages | 10 |

Journal | Computer Journal |

Volume | 38 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1995 |

Externally published | Yes |