Skip to main content

The pipelined set cover problem

Publication ,  Journal Article
Munagala, K; Babu, S; Motwani, R; Widom, J
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
December 1, 2005

A classical problem in query optimization is to find the optimal ordering of a set of possibly correlated selections. We provide an abstraction 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 data-stream 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 lp-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. © 2005 Springer-Verlag.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2005

Volume

3363 LNCS

Start / End Page

83 / 98

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Munagala, K., Babu, S., Motwani, R., & Widom, J. (2005). The pipelined set cover problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3363 LNCS, 83–98. https://doi.org/10.1007/978-3-540-30570-5_6
Munagala, K., S. Babu, R. Motwani, and J. Widom. “The pipelined set cover problem.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3363 LNCS (December 1, 2005): 83–98. https://doi.org/10.1007/978-3-540-30570-5_6.
Munagala K, Babu S, Motwani R, Widom J. The pipelined set cover problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005 Dec 1;3363 LNCS:83–98.
Munagala, K., et al. “The pipelined set cover problem.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3363 LNCS, Dec. 2005, pp. 83–98. Scopus, doi:10.1007/978-3-540-30570-5_6.
Munagala K, Babu S, Motwani R, Widom J. The pipelined set cover problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005 Dec 1;3363 LNCS:83–98.

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2005

Volume

3363 LNCS

Start / End Page

83 / 98

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences