Parallel K-set mutual range-join in hypercubes

Hong Shen

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

The mutual range-join of k sets, S1, S2,..., Sk, is the set containing all tuples (s1, s2..., sk) that satisfy 1 ≤ |si - sj | ≤ e2 for all 1 ≤i≠j≤k, where si ε{lunate} Si and e1 ≤ e2 are fixed constants. This paper presents an efficient parallel algorithm for computing the k-set mutual range-join in hypercube computers. The proposed algorithm uses a fast method to determine whether the differences of all pair numbers among k given numbers are within a given range and applies the technique of permutation-based range-join [11]. To compute the mutual range-join of k sets S1,S2,..., Sk in a hypercube of p processors with O(∑ki = 1nini/p) local memory, p ≤ |Si| = ni and 1 ≤ i ≤ k, our algorithm requires at most O((k log k/p)πki = 1ni) data comparisons in the worst case. The algorithm is implemented in PVM and its performance is extensively evaluated on various input data.

Original languageEnglish
Pages (from-to)443-448
Number of pages6
JournalMicroprocessing and Microprogramming
Volume41
Issue number7
DOIs
Publication statusPublished - Nov 1995
Externally publishedYes

Keywords

  • Data comparison
  • Hypercube
  • Parallel algorithm
  • Permutation
  • Range-join

Fingerprint

Dive into the research topics of 'Parallel K-set mutual range-join in hypercubes'. Together they form a unique fingerprint.

Cite this