Adaptive Precision Setting for Cached Approximate Values
Chris Olston, Boon Thau Loo, and Jennifer Widom
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.
Conference Paper (SIGMOD 2001): [PS], [PDF]. Citation: [BibTeX]
Algorithm Demo: [Java]
TRAPP Project Web Page: [HTML]