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

Shao Dong Chen, Hong Shen, Rodney Topor

研究成果: Conference contribution同行評審

5 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Algorithms, Concurrency and Knowledge - 1995 Asian Computing Science Conference, ACSC 1995, Proceedings
編輯Kanchana Kanchanasut, Jean-Jacques Levy
發行者Springer Verlag
頁面225-238
頁數14
ISBN(列印)3540606882, 9783540606888
DOIs
出版狀態Published - 1995
對外發佈
事件Asian Computing Science Conference, ACSC 1995 - Pathumthani, Thailand
持續時間: 11 12月 199513 12月 1995

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
1023
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

ConferenceAsian Computing Science Conference, ACSC 1995
國家/地區Thailand
城市Pathumthani
期間11/12/9513/12/95

指紋

深入研究「Efficient parallel permutation-based range-join algorithms on mesh-connected computers」主題。共同形成了獨特的指紋。

引用此