The Pipelined Set Cover Problem
The Pipelined Set Cover Problem
复制标题
流水线集覆盖问题
DOI：
10.1007/978-3-540-30570-5_6
复制
发表时间：
2005
期刊：
影响因子：
1.1
通讯作者：
J. Widom
中科院分区：
文献类型：
--
作者：
Kamesh Munagala;S. Babu;R. Motwani;J. Widom
查询优化中的一个经典问题是找到一组可能相关的选择的最优排序。我们给出了这个问题的一个推广，称为流水线集合覆盖，其中集合被顺序地应用于要覆盖的元素，而在每个阶段被覆盖的元素被丢弃。我们证明了这个NP-Hard问题的几个自然启发式算法，如贪婪集覆盖启发式算法和局部搜索启发式算法，可以用线性规划框架来分析。这些启发式算法导致了用于流水线集合覆盖的高效算法，该算法可以应用于对传统数据库系统以及数据流处理系统中可能相关的选择进行排序。我们使用我们的线性规划框架证明了贪婪算法和局部搜索算法是流水线集合覆盖的4-近似算法。我们将我们的分析扩展到最小化集合所支付费用的L P-范数，其中p>；2为整数，以检验当总成本对流水线中初始集合的贡献增加时对性能的改善。最后，我们考虑了在线版本的流水线集合覆盖，并给出了一个具有对数性能保证的竞争性算法。我们的分析框架可能适用于查询优化中的其他问题，其中考虑相关性非常重要。
A classical problem in query optimization is to find the optimal ordering of a set of possibly correlated selections. We provide an ion of this problem as a generalization of set cover called pipelined set cover, where the sets are applied sequentially to the elements to be covered and the elements covered at each stage are discarded. We show that several natural heuristics for this NP-hard problem, such as the greedy set-cover heuristic and a local-search heuristic, can be analyzed using a linear-programming framework. These heuristics lead to efficient algorithms for pipelined set cover that can be applied to order possibly correlated selections in conventional database systems as well as datastream processing systems. We use our linear-programming framework to show that the greedy and local-search algorithms are 4-approximations for pipelined set cover. We extend our analysis to minimize the l P -norm of the costs paid by the sets, where p > 2 is an integer, to examine the improvement in performance when the total cost has increasing contribution from initial sets in the pipeline. Finally, we consider the online version of pipelined set cover and present a competitive algorithm with a logarithmic performance guarantee. Our analysis framework may be applicable to other problems in query optimization where it is important to account for correlations.