Papers for

cdn operators

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Weighted caching improved using predictions under known request patterns

Stochastic Weighted Caching with Per-Request Predictions

Abstract: Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of $Θ(\log k)$, where $k$ is the cache size. We study weighted caching with per-request predictions, where each page request is accompanied by a prediction of the next arrival time of the same page. For unweighted caching, such perfect predictions suffice to implement Belady's offline optimal rule. For weighted caching, however, previous work shows that a logarithmic lower bound persists even with perfect predictions on adversarial request sequences. Stochastic assumptions alone are also insufficient: the classical caching lower bounds already apply to uniform independent requests. In this work, we ask whether combining these two sources of additional information can overcome this barrier, and answer this question affirmatively. Specifically, we develop an efficient, deterministic cache eviction policy that achieves a competitive ratio of $15.75$ using perfect per-request predictions when page requests are drawn independently from an arbitrary, known static distribution in every step, and page costs are arbitrary. Our algorithm's performance degrades gracefully under erroneous predictions: we prove a bound of $O(\min\{1+E,\log k\})$ on the competitive ratio, where $E$ aggregates each page's average prediction error, and may be unknown to the algorithm.

Mon 12 OctData Structures and Algorithms
The gist
Caching is about storing limited items so future requests are faster or cheaper. The authors study caching when every request comes with a prediction of when it will happen again. While perfect predictions solve simple caching, it remains hard for weighted caching where items have different costs. They show that if requests happen randomly but with a known fixed pattern, perfect predictions can achieve a good eviction strategy with a fixed competitive ratio. Their approach also handles imperfect predictions gracefully, improving caching efficiency when predictions are somewhat accurate.
Open → 2610.16045v1