title: Computing the Median With Uncertainty
creator: Feder, T.
creator: Motwani, R.
creator: Panigrahy, R.
creator: Olston, C.
creator: Widom, J.
subject: Data Mining
description: We consider a new model for computing with uncertainty.  It is desired to compute a function f(X_1,...,X_n) where X_1,...,X_n are unknown, but guaranteed to lie in specified intervals I_1,...,I_n. It is possible to query the precise value of any X_j at a cost c_j. The goal is to pin down the value of f to within a precision p at a minimum possible cost. We focus on the selection function f which returns the value of the kth smallest argument. We present optimal offline and online algorithms for this problem.
publisher: Stanford InfoLab
date: 1999
type: Techreport
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/397/1/1999-41.pdf
identifier: Feder, T. and Motwani, R. and Panigrahy, R. and Olston, C. and Widom, J. (1999) Computing the Median With Uncertainty. Technical Report. Stanford InfoLab. (Publication Note: 32nd ACM Symposium on Theory of Computing (STOC 2000), Portland, Oregon, May 2000)
relation: http://ilpubs.stanford.edu:8090/397/