Efficient parallel permutation-based range-join algorithms on mesh-connected computers

Shao Dong Chen, Hong Shen, Rodney Topor

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

Abstract

This paper proposes three efficient parallel algorithms for computing the range-join of two relations on two-dimensional n x m mesh-connected computers, where n and m are the numbers of the rows and columns respectively. After sorting all subsets of both relations, all proposed algorithms permute all sorted subsets of one relation to each processor in the computers, where they are joined with the subset of the other relation at that processor by using a sequential sort-merge rangejoin algorithm. The Min-Storage-Shifting and Min-Movement-Shifting algorithms permute the data on a mesh alternatively in the row and column directions, and Hamiltonian-cycle algorithm permutes the data along a Hamiltonian cycle of the mesh. The analysis shows that the Hamiltonian-cycle algorithm requires fewer local join operations but more data movements than other two algorithms and that the Min-Movement-Shifting algorithm requires fewer local join operations and data movements but more storage than the Min-Storage-Shifting algorithm.

Original languageEnglish
Title of host publicationAlgorithms, Concurrency and Knowledge - 1995 Asian Computing Science Conference, ACSC 1995, Proceedings
EditorsKanchana Kanchanasut, Jean-Jacques Levy
PublisherSpringer Verlag
Pages225-238
Number of pages14
ISBN (Print)3540606882, 9783540606888
DOIs
Publication statusPublished - 1995
Externally publishedYes
EventAsian Computing Science Conference, ACSC 1995 - Pathumthani, Thailand
Duration: 11 Dec 199513 Dec 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1023
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceAsian Computing Science Conference, ACSC 1995
Country/TerritoryThailand
CityPathumthani
Period11/12/9513/12/95

Keywords

  • Analytic cost models
  • Mesh-connected multiple computers
  • Parallel algorithms
  • Parallel query optimization
  • Rangejoin
  • Relational databases

Fingerprint

Dive into the research topics of 'Efficient parallel permutation-based range-join algorithms on mesh-connected computers'. Together they form a unique fingerprint.

Cite this