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 - https://www.scopus.com/pages/publications/84947909990
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 -