Asking the right questions: Model-driven optimization using probes

Journal Article

In several database applications, parameters like selectivities and load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of query optimizers and monitoring schemes can be improved by spending resources like time or bandwidth in observing or resolving these parameters, so that better query plans can be generated. In a resource-constrained situation, deciding which parameters to observe in order to best optimize the expected quality of the plan generated (or in general, optimize the expected value of a certain objective function) itself becomes an interesting optimization problem.We present a framework for studying such problems, and present several scenarios arising in anomaly detection in complex systems, monitoring extreme values in sensor networks, load shedding in data stream systems, and estimating rates in wireless channels and minimum latency routes in networks, which can be modeled in this framework with the appropriate objective functions.Even for several simple objective functions, we show the problems are Np-Hard. We present greedy algorithms with good performance bounds. The proof of the performance bounds are via novel sub-modularity arguments. Copyright 2006 ACM.

Full Text

Duke Authors

Cited Authors

  • Goel, A; Guha, S; Munagala, K

Published Date

  • December 1, 2006

Published In

  • Proceedings of the Acm Sigact Sigmod Sigart Symposium on Principles of Database Systems

Start / End Page

  • 203 - 212

Digital Object Identifier (DOI)

  • 10.1145/1142351.1142380

Citation Source

  • Scopus