TY - GEN

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

AU - Chen, Shao Dong

AU - Shen, Hong

AU - Topor, Rodney

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

KW - Analytic cost models

KW - Mesh-connected multiple computers

KW - Parallel algorithms

KW - Parallel query optimization

KW - Rangejoin

KW - Relational databases

UR - http://www.scopus.com/inward/record.url?scp=84947909990&partnerID=8YFLogxK

U2 - 10.1007/3-540-60688-2_47

DO - 10.1007/3-540-60688-2_47

M3 - Conference contribution

AN - SCOPUS:84947909990

SN - 3540606882

SN - 9783540606888

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 225

EP - 238

BT - Algorithms, Concurrency and Knowledge - 1995 Asian Computing Science Conference, ACSC 1995, Proceedings

A2 - Kanchanasut, Kanchana

A2 - Levy, Jean-Jacques

PB - Springer Verlag

T2 - Asian Computing Science Conference, ACSC 1995

Y2 - 11 December 1995 through 13 December 1995

ER -