Stanford InfoLab Publication Server

Computing the Median With Uncertainty

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)

WarningThere is a more recent version of this item available.



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.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:TRAPP, replication system, bounded replication
Subjects:Computer Science > Data Mining
Related URLs:Project Homepage, Project Homepage,
ID Code:397
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:28 Dec 2008 08:59

Available Versions of this Item

Download statistics

Repository Staff Only: item control page