[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2001-18 | ||
| Previous version | 2000-32 | ||
| Submitted on | 14th of May 2001 | ||
| Author | Olston, Chris; Loo, Boon Thau; Widom, Jennifer | ||
| Title | Adaptive Precision Setting for Cached Approximate Values | ||
| Date of publication | 21st of May 2001 | ||
| Published in | 2001 ACM SIGMOD International Conference on Management of Data | ||
| Citation | Olston, Chris; Loo, Boon Thau; Widom, Jennifer. Adaptive Precision Setting for Cached Approximate Values, 2001 ACM SIGMOD International Conference on Management of Data | ||
| Number of pages | 12 | ||
| Language | English | ||
| Project | TRAPP | ||
| Type | Conference or Journal Paper | ||
| Subject group | Distributed Systems | ||
| Abstract | Caching approximate values instead of exact values presents an opportunity for performance gains in exchange for decreased precision. To maximize the performance improvement, cached approximations must be of appropriate precision: approximations that are too precise easily become invalid, requiring frequent refreshing, while overly imprecise approximations are likely to be useless to applications, which must then bypass the cache. We present a parameterized algorithm for adjusting the precision of cached approximations adaptively to achieve the best performance as data values, precision requirements, or workload vary. We consider interval approximations to numeric values but our ideas can be extended to other kinds of data and approximations. Our algorithm strictly generalizes previous adaptive caching algorithms for exact copies: we can set parameters to require that all approximations be exact, in which case our algorithm dynamically chooses whether or not to cache each data value. We have implemented our algorithm and tested it on synthetic and real-world data. A number of experimental results are reported, showing the effectiveness of our algorithm at maximizing performance, and also showing that in the special case of exact caching our algorithm performs as well as previous algorithms. In cases where bounded imprecision is acceptable, our algorithm easily outperforms previous algorithms for exact caching. | ||
| Keywords | approximate caching, precision-setting, distributed databases | ||
| Contact address | olston@db.stanford.edu | ||
| Sponsored by |
This work was supported by the National Science Founda-tion under grant IIS-9811947,and by a National Science Foundation graduate research fellowship. | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]