[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/1999-41 | ||
| Next version(s) | 2002-50 | ||
| Submitted on | 26th of February 2000 | ||
| Author | Feder, T.; Motwani, R.; Panigrahy, R.; Olston, C.; Widom, J. | ||
| Title | Computing the Median With Uncertainty | ||
| Date of publication | 1999 | ||
| Citation | T. Feder,R. Motwani,R. Panigrahy,C. Olston,J. Widom: Computing the Median With Uncertainty. 32nd ACM Symposium on Theory of Computing (STOC 2000), Portland, Oregon, May 2000. | ||
| Language | English | ||
| Project | MIDAS; TRAPP | ||
| Type | Conference or Journal Paper | ||
| Subject group | Data Mining | ||
| 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. | ||
| Keywords | TRAPP, replication system, bounded replication | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]