An efficient permutation-based parallel algorithm for range-join in hypercubes

Hong Shen

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

The range-join of sets R and S is defined to be the set containing all tuples (r, s) that satisfy e1 ≤ |r - s| ≤ e2, where r ε{lunate} R, s ε{lunate} S, e1, and e2 are fixed constants. This paper proposes an efficient parallel range-join algorithm in hypercubes. To compute the range-join of two sets R and S on a hypercube of p processors (p ≤ |R| = m ≤ |S| = n), the proposed algorithm simply permutes the elements of R to obtain their possible combinations with the elements of S and thus all possible local range-joins. Requiring only O( (m + n) p) local memory at each processor, our algorithm has a time complexity O((( n p) + m) log( n p)) in the best case when no element in S matches any element in R; O(Tksort + ( m p)) in the worst case when all elements in S match each element in R, where Tksort = O(k log k) when all elements in S are distinct, and Tksort = O(k) when all elements in S are equal, k = n p. The general-case time complexity of the algorithm is also shown.

Original languageEnglish
Pages (from-to)303-313
Number of pages11
JournalParallel Computing
Volume21
Issue number2
DOIs
Publication statusPublished - Feb 1995
Externally publishedYes

Keywords

  • Hypercube
  • Parallel algorithms
  • Permuting
  • Processors
  • Range-join
  • Time complexity

Fingerprint

Dive into the research topics of 'An efficient permutation-based parallel algorithm for range-join in hypercubes'. Together they form a unique fingerprint.

Cite this