An Improved Approximation Algorithm for Pipelined Operator Tree Scheduling

摘要：

Pipelined operator tree (POT) scheduling is an important problem in the area of parallel query optimization. A POT is a tree with nodes representing query operators that can run in parallel and edges representing communication between adjacent operators that is handled by sending long streams of data in a parallel-pipelined fashion. The problem is to assign operators to processors so as to minimize the maximum processor load. Chekuri et al. developed two algorithms for this NP-hard problem with performance ratios 3.56 and 87. 2)1 (ε +respectively, where 0 >ε can be made arbitrarily small. We present a)2 (ε +-approximation algorithm.

关键词： query optimization parallel databases pipelined operator tree scheduling maximum load approximation algorithms

作者: Li Shuguang Xin Xiao

作者单位: College of Computer Science and TechnologyShandong Institute of Business and TechnologyYantai, China College of Foreign Studies Shandong Institute of Business and Technology Yantai, China

会议类型: 国际会议

会议名称: 2010 3rd International Conference on Advanced Computer Theory and Engineering(2010年第三届先进计算机理论与工程国际会议 ICACTE 2010)

会议地点: 成都

会议语种:英文

页码: 1-4

在线出版日期: 2010-08-20（万方平台首次上网日期，不代表论文的发表时间）