首个无需预先知道页面权重的在线加权缓存算法，通过采样学习权重。
Online Weighted Paging with Unknown Weights
- 通过多次采样页面获取成本，动态学习未知权重。
- 首次实现无需先验权重的在线加权缓存，达到理论最优竞争比。
- 适用于多级缓存等实际场景，可推广至其他需成本采样的在线问题。
在线缓存是在线算法领域的基础问题，需在请求到来时维护一个大小为 $k$ 的缓存。在加权变体中，每页具有独立的获取代价；此前研究已给出最优的 $O(\log k)$-竞争比随机算法（Bansal, Buchbinder and Naor, FOCS'07）。但现有工作假设页面权重已知，这在实践中并不总成立。例如在多级缓存架构中，获取内存块的预期成本取决于其位于中间缓存而非主存的概率，该属性无法预先预测。然而，可通过多次采样获取成本逐步推断权重。本文提出首个无需预先知晓页面权重的在线加权缓存算法，而是通过采样学习权重。技术上，需向分数解求解器提供整数样本，要求解求解器与随机舍入方案间有精巧接口；我们相信该方法可启发其他涉及成本采样的在线算法设计。
原文摘要 · Abstract (English)
Online paging is a fundamental problem in the field of online algorithms, in which one maintains a cache of $k$ slots as requests for fetching pages arrive online. In the weighted variant of this problem, each page has its own fetching cost; a substantial line of work on this problem culminated in an (optimal) $O(\log k)$-competitive randomized algorithm, due to Bansal, Buchbinder and Naor (FOCS'07). Existing work for weighted paging assumes that page weights are known in advance, which is not always the case in practice. For example, in multi-level caching architectures, the expected cost of fetching a memory block is a function of its probability of being in a mid-level cache rather than the main memory. This complex property cannot be predicted in advance; over time, however, one may glean information about page weights through sampling their fetching cost multiple times. We present the first algorithm for online weighted paging that does not know page weights in advance, but rather learns from weight samples. In terms of techniques, this requires providing (integral) samples to a fractional solver, requiring a delicate interface between this solver and the randomized rounding scheme; we believe that our work can inspire online algorithms to other problems that involve cost sampling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。