A Parallel Scheme Using the Divide-and-Conquer Method Article

Yang, Q, Dao, S, Yu, C et al. (1997). A Parallel Scheme Using the Divide-and-Conquer Method . DISTRIBUTED AND PARALLEL DATABASES, 5(4), 405-438. 10.1023/A:1008688512013

cited authors

  • Yang, Q; Dao, S; Yu, C; Rishe, N

authors

abstract

  • A parallel scheme using the divide-and-conquer method is developed. This partitions the input set of a problem into subsets, computes a partial result from each subset, and finally employs a merging function to obtain the final answer. Based on a linear recursive program as a tool for formalism, a precise characterization for problems to be parallelized by the divide-and-conquer method is obtained. The performance of the parallel scheme is analyzed, and a necessary and sufficient condition to achieve linear speedup is obtained. The parallel scheme is generalized to include parameters, and a real application, the fuzzy join problem, is discussed in detail using the generalized scheme.

publication date

  • January 1, 1997

published in

Digital Object Identifier (DOI)

start page

  • 405

end page

  • 438

volume

  • 5

issue

  • 4