Parallel Algorithms for Partitioning Sorted Sets and Related Problems |
| |
Authors: | D Z Chen W Chen K Wada K Kawaguchi |
| |
Affiliation: | (1) Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA. chen@cse.nd.edu., US;(2) Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa, Nagoya 466, Japan. chen@elcom.nitech.ac.jp, wada@elcom.nitech.ac.jp, kawaguchi@elcom.nitech.ac.jp., JP |
| |
Abstract: | We consider the following partition problem: Given a set S of n elements that is organized as k sorted subsets of size n/k each and given a parameter h with 1/k ≤ h ≤ n/k , partition S into g = O(n/(hk)) subsets D
1
, D
2
, . . . , D
g
of size Θ(hk) each, such that, for any two indices i and j with 1 ≤ i < j ≤ g , no element in D
i
is bigger than any element in D
j
. Note that with various combinations of the values of parameters h and k , several fundamental problems, such as merging, sorting, and finding an approximate median, can be formulated as or be reduced
to this partition problem. The partition problem also finds many applications in solving problems of parallel computing and
computational geometry. In this paper we present efficient parallel algorithms for solving the partition problem and a number
of its applications. Our parallel partition algorithm runs in O( log n) time using processors in the EREW PRAM model. The complexity bounds of our parallel partition algorithm on the respective special cases
match those of the optimal EREW PRAM algorithms for merging, sorting, and finding an approximate median. Using our parallel
partition algorithm, we are also able to obtain better complexity bounds (even possibly on a weaker parallel model) than the
previously best known parallel algorithms for several important problems, including parallel multiselection, parallel multiranking,
and parallel sorting of k sorted subsets.
Received May 5, 1996; revised July 30, 1998. |
| |
Keywords: | , Algorithms, EREW PRAM, Merging, Multiselection, Partitioning, Sorting, Parallel computing, |
本文献已被 SpringerLink 等数据库收录! |
|