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)
| BibTeX | DublinCore | EndNote | HTML |
 | There is a more recent version of this item available. |
![[img]](/style/images/fileicons/application_pdf.png)
| PDF 211Kb |
Abstract
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 | |
| Projects: | MIDAS TRAPP | |
| Related URLs: | Project Homepage, Project Homepage | http://infolab.stanford.edu/midas/midas.html, http://infolab.stanford.edu/trapp/ |
| 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
- Computing the Median With Uncertainty. (deposited 25 Feb 2000 16:00) [Currently Displayed]
Download statistics
Repository Staff Only: item control page
