On computing functions with uncertainty

ABSTRACT

We study the problem of computing a function f(x1,…, xn) given that the actual values of the variables xi's are known only with some uncertainty. For each variable xi, an interval Ii is known such that the value of xi is guaranteed to fall within this interval. Any such interval can be probed to obtain the actual value of the underlying variable; however, there is a cost associated with each such probe. The goal is to adaptively identify a minimum cost sequence of probes such that regardless of the actual values taken by the unprobed xi's, the value of the function f can be computed to within a specified precision.

We design online algorithms for this problem when f is either the selection function or an aggregation function such as sum or average. We consider three natural models of precision and give algorithms for each model. We analyze our algorithms in the framework of competitive analysis and show that our algorithms are asymptotically optimal. Finally, we also study online algorithms for functions that are obtained by composing together selection and aggregation functions.

REFERENCES

• 1: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 2: Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States
• 3: Surajit Chaudhuri , Luis Gravano, Evaluating Top-k Selection Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.397-410, September 07-10, 1999
• 4: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 5: Ronald Fagin, Fuzzy queries in multimedia database systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275488]
• 6: Tomas Feder , Rajeev Motwani , Rina Panigrahy , Chris Olston , Jennifer Widom, Computing the median with uncertainty, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.602-607, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335386]
• 7: Hector Garcia-Molina , Steven P. Ketchpel , Narayanan Shivakumar, Safeguarding and Charging for Information on the Internet, Proceedings of the Fourteenth International Conference on Data Engineering, p.182-189, February 23-27, 1998
• 8: M. C. Golumbic. Algorithmic Graph Theory. Academic Press, 1980.
• 9: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 10: Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Performance, Theory