Asking the right questions: model-driven optimization using probes

ABSTRACT

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.

REFERENCES

• 1: Aditya Akella , Bruce Maggs , Srinivasan Seshan , Anees Shaikh , Ramesh Sitaraman, A measurement-based analysis of multihoming, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863995]
• 2: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 3: Brian Babcock , Surajit Chaudhuri, Towards a robust query optimizer: a principled and practical approach, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066172]
• 4: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 5: Shivnath Babu , Pedro Bizarro , David DeWitt, Proactive re-optimization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066171]
• 6: Robert D. Carr , Lisa K. Fleischer , Vitus J. Leung , Cynthia A. Phillips, Strengthening integrality gaps for capacitated network design and covering problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.106-115, January 09-11, 2000, San Francisco, California, United States
• 7: Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.582-591, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335382]
• 8: Francis Chu , Joseph Halpern , Johannes Gehrke, Least expected cost query optimization: what can we expect?, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543651]
• 9: Francis Chu , Joseph Y. Halpern , Praveen Seshadri, Least expected cost query optimization: an exercise in utility, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-147, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303990]
• 10: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 11: A. Deshpande, C. Guestrin, S. Madden, J. M. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In Proc. of the 2004 Intl. Conf. on Very Large Data Bases, 2004.
• 12: Tomás Feder , Rajeev Motwani , Rina Panigrahy , Chris Olston , Jennifer Widom, Computing the Median with Uncertainty, SIAM Journal on Computing, v.32 n.2, p.538-547, 2003 [doi>10.1137/S0097539701395668]
• 13: Ashish Goel , Piotr Indyk, Stochastic Load Balancing and Related Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.579, October 17-18, 1999
• 14: P. K. Gummadi, H. V. Madhyastha, S. D. Gribble, H. M. Levy, and D. Wetherall. Improving the reliability of internet paths with one-hop source routing. In 6th Symposium on Operating System Design and Implementation (OSDI), pages 183--198, 2004.
• 15: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 16: Anupam Gupta , R. Ravi , Amitabh Sinha, An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.218-227, October 17-19, 2004 [doi>10.1109/FOCS.2004.11]
• 17: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 18: Sanjeev Khanna , Wang-Chiew Tan, On computing functions with uncertainty, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.171-182, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375577]
• 19: Jon Kleinberg , Yuval Rabani , Éva Tardos, Allocating Bandwidth for Bursty Connections, SIAM Journal on Computing, v.30 n.1, p.191-217, 2000 [doi>10.1137/S0097539797329142]
• 20: S. Kolliopoulos , N. Young, Tight Approximation Results for General Covering Integer Programs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.522, October 14-17, 2001
• 21: A. Krause and C. Guestrin. Near-optimal nonmyopic value of information in graphical models. Twenty-first Conference on Uncertainty in Artificial Intelligence (UAI 2005), 2005.
• 22: M. L. Massie, B. N. Chun, and D. E. Culler. The Ganglia distributed monitoring system: Design, implementation, and experience. Parallel Computing, 30(7), 2004.
• 23: G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-I. Math Programming, 14(1):265--294, 1978.
• 24: Christopher Alden Remi Olston , Jennifer Widom, Approximate replication, 2003
• 25: David B. Shmoys , Chaitanya Swamy, Stochastic Optimization is (Almost) as easy as Deterministic Optimization, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 26: Adam Silberstein Silberstein , Rebecca Braynard , Carla Ellis , Kamesh Munagala , Jun Yang, A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.68, April 03-07, 2006 [doi>10.1109/ICDE.2006.10]
• 27: N. Tatbul, U. Etintemel, S. Zdonik, M. Chemiack, and M. Stonebraker. Load shedding in a data stream manager. In Proc. of the Intl. Conf. on Very Large Data Bases, 2003.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory