Large-scale uncertainty management systems: learning and exploiting your data

ABSTRACT

The database community has made rapid strides in capturing, representing, and querying uncertain data. Probabilistic databases capture the inherent uncertainty in derived tuples as probability estimates. Data acquisition and stream systems can produce succinct summaries of very large and time-varying datasets. This tutorial addresses the natural next step in harnessing uncertain data: How can we efficiently and quantifiably determine what, how, and how much to learn in order to make good decisions based on the imprecise information available.

The material in this tutorial is drawn from a range of fields including database systems, control and information theory, operations research, convex optimization, and statistical learning. The focus of the tutorial is on the natural constraints that are imposed in a database context and the demands of imprecise information from an optimization point of view. We look both into the past as well as into the future; to discuss general tools and techniques that can serve as a guide to database researchers and practitioners, and to enumerate the challenges that lie ahead.

REFERENCES

• 1: J. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pages 263--274, 2008.
• 2: Barbara M. Anthony , Vineet Goyal , Anupam Gupta , Viswanath Nagarajan, A plant location guide for the unsure, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1164-1173, January 20-22, 2008, San Francisco, California
• 3: 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
• 4: Baruch Awerbuch , Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007367]
• 5: 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]
• 6: S. Babu. Grand challenge: Experiment-driven adaptive systems. In Proc. Hot Topics in Autonomic Computing (HotAC III), 2008.
• 7: S. Babu, N. Borisov, S. Duan, H. Herodotou, and V. Thummala. Automated experiment-driven management of (database) systems. In Proceedings of Workshop on Hot Topics in Operating Systems (HotOS), 2009.
• 8: Songyun Duan , Shivnath Babu , Kamesh Munagala, Fa: A System for Automating Failure Diagnosis, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1012-1023, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.115]
• 9: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 10: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 11: Graham Cormode , Andrew McGregor, Approximation algorithms for clustering uncertain data, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376944]
• 12: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 13: Amol Deshpande , Sunita Sarawagi, Probabilistic graphical models and their role in databases, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 14: Songyun Duan , Shivanath Babu, Processing forecasting queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 15: Abraham D. Flaxman , Adam Tauman Kalai , H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: J.C. Gittins and D.M. Jones. A dynamic allocation index for the sequential design of experiments. Progress in statistics (European Meeting of Statisticians), 1972.
• 17: Ashish Goel , Sudipto Guha , Kamesh Munagala, Asking the right questions: model-driven optimization using probes, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142380]
• 18: Sudipto Guha , Kamesh Munagala, Approximation algorithms for budgeted learning problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250807]
• 19: Sudipto Guha , Kamesh Munagala, Model-driven optimization using adaptive probes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.308-317, January 07-09, 2007, New Orleans, Louisiana
• 20: Sudipto Guha , Kamesh Munagala, Exceeding expectations and clustering uncertain data, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA [doi>10.1145/1559795.1559836]
• 21: S. Guha, K. Munagala, and S. Sarkar. Information acquisition and exploitation in multi-channel wireless systems. CoRR: 0804.1724, 2008.
• 22: S. Guha, K. Munagala, and P. Shi. Approximation algorithms for restless bandit problems. CoRR: 0711.3861, 2008.
• 23: Rahul Gupta , Sunita Sarawagi, Creating probabilistic databases from information extraction models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 24: P. Horn. Autonomic computing: IBM's perspective on the state of information technology. IBM Tech. Rep., 2001. http://www.research.ibm.com/autonomic.
• 25: 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]
• 26: A. Krause and C. Guestrin. Near-optimal nonmyopic value of information in graphical models. UAI, 2005.
• 27: Andreas Krause , Carlos Guestrin , Anupam Gupta , Jon Kleinberg, Near-optimal sensor placements: maximizing information while minimizing communication cost, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127782]
• 28: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 29: Laszlo Lovasz , Santosh Vempala, Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.57-68, October 21-24, 2006 [doi>10.1109/FOCS.2006.28]
• 30: K. Munagala, S. Babu, R. Motwani, and J. Widom. The pipelined set cover problem. Proc. Intl. Conf. Database Theory, 2005.
• 31: 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.
• 32: S. Pandey and C. Olston. Handling advertisements of unknown quality in search advertising. In NIPS, pages 1065--1072, 2006.
• 33: H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527--535, 1952.
• 34: S. Sarawagi and W.W. Cohen. Semi-Markov conditional random fields for information extraction. Proc. NIPS, 2004.
• 35: Atish Das Sarma , Sreenivas Gollapudi , Samuel Ieong, Bypass rates: reducing query abandonment using negative inferences, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401916]
• 36: Piyush Shivam , Shivnath Babu , Jeff Chase, Active and accelerated learning of cost models for optimizing scientific applications, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 37: Adam Silberstein , Gavino Puggioni , Alan Gelfand , Kamesh Munagala , Jun Yang, Suppression and failures in sensor networks: a Bayesian approach, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 38: James C. Spall, Introduction to Stochastic Search and Optimization, John Wiley & Sons, Inc., New York, NY, 2003
• 39: Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom, Operator placement for in-network stream query processing, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065199]
• 40: Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom , Rajeev Motwani, Query optimization over web services, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 41: R. Thonangi, V. Thummala, and S. Babu. Finding good configurations in high-dimensional spaces: Doing more with less. In Proc. MASCOTS, 2008.
• 42: P. Whittle. Restless bandits: Activity allocation in a changing world. Appl. Prob., 25(A):287--298, 1988.
• 43: M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. Proceedings of ICML, pages 928--936, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Measurement, Performance

Keywords:
algorithms, measurement, performance tuning