nucleation

LIT-1109: Adaptive Precision Setting for Cached Approximate Values

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the copy in the University of Pennsylvania's repository (ScholarlyCommons cis_papers 1351, repository.upenn.edu/server/api/core/bitstreams/92340f91-673c-435e-9b4e-b24072d4d96b/content), the camera-ready text with printed pages 355–366. Worth reading as the one model the record holds in which staleness and upkeep are traded in a single objective: a cached interval of width W is escaped (a pushed refresh, cost C_vr) more often when narrow and is too loose for queries (an exact fetch, cost C_qr) more often when wide, and under the paper's model the least expected cost is where ρ·P_vr = P_qr with ρ = 2C_vr/C_qr (THEORY-386); a rule that widens on one kind of refresh and narrows on the other came within 1–5% of the best fixed width in simulation and, restricted to exact copies, matched an adaptive cache-or-not algorithm (THEORY-377). For QUESTION-114 it prices staleness as refresh traffic, with no build cost, no stored answers and no cost of a wrong answer, since the source guarantees validity. For CLAIM-303 it gives upkeep and per-use verification a common dial, but only where a source sees every change; for CLAIM-308 its exact-caching case is a forecast-free counting rule justified in expectation, not in the worst case, and once staleness is admitted the two-state choice becomes a continuum with an interior optimum.
Tagsdatabases, operations-research
Cited as “paper” byNOTE-912 — Olston, Loo & Widom — Adaptive precision setting for cached approximate values
Cited as “source” byTHEORY-377 — In Olston, Loo and Widom's simulations, a rule that multiplies a cached interval's width by 1 + α on a pushed refresh with probability min{ρ, 1}, and divides it by 1 + α on a query's exact fetch with probability min{1/ρ, 1}, settled within 1% of the best fixed width on one random walk and within 5% over eight walk settings; on a 50-host network-traffic trace, restricted to exact copies, it almost matched a tuned adaptive cache-or-not rule, and with a 50-value cache, where queries tolerated imprecision, it cost less; that it converges to the best width is argued, not proved, THEORY-386 — When a cached interval of width W is kept valid by its source, which pushes a refresh at cost C_vr whenever the value leaves it, and queries fetch the exact value at cost C_qr whenever it is too wide, and the chances of the two per step go as 1/W² and as W, the expected refresh cost is least at W* = (ρK₁/K₂)^(1/3) with ρ = 2C_vr/C_qr, where ρ times the chance of a pushed refresh equals the chance of a fetch

Graph View

Olston, C., Loo, B. T. and Widom, J. (2001). Adaptive precision setting for cached approximate values. In Proc. ACM SIGMOD 2001, pp. 355–366. DOI 10.1145/375663.375710

Key takeaways

Read in full (NOTE-912). Olston, Loo and Widom set the width of each cached interval adaptively to minimize total refresh traffic. A narrow interval is escaped often (value-initiated refreshes, cost C_vr); a wide one is too imprecise for queries more often (query-initiated refreshes, cost C_qr). Under a model in which these probabilities go as 1/W² and W, the expected cost rate is least where ρ·P_vr = P_qr, ρ = 2C_vr/C_qr, and a rule that widens on value-initiated and narrows on query-initiated refreshes, with probabilities set by ρ, reached within 1% to 5% of the best fixed width in simulation. That the rule converges is argued, not proved. With exact copies required it matched an adaptive exact-caching algorithm, and where imprecision was allowed it beat it. Staleness is priced as refresh traffic only: there is no build cost, no cost of a wrong answer, and the interval is never wrong.

Why this is here

QUESTION-114 and CLAIM-303: sets each cached interval’s width to balance pushed refreshes against exact fetches by queries, the first model the record holds with upkeep and tolerated staleness in one objective and an optimum between them. It assumes a source that sees every change, which a filed argument lacks.

Backlinks