摘要 —本文重点介绍相似性缓存系统,其中用户对不在缓存中的对象 𝑜 的请求可以通过存储的相似对象 𝑜 ′ 来(部分)满足,但代价是用户效用的损失。相似性缓存系统可有效地用于多个应用领域,如多媒体检索、推荐系统、基因组研究和机器学习训练/服务。然而,尽管它们具有相关性,但人们对此类系统的行为还远未得到很好的理解。在本文中,我们首次全面分析了离线、对抗和随机设置中的相似性缓存。我们表明相似性缓存带来了重大的新挑战,为此我们提出了第一个具有一些最优性保证的动态策略。我们在合成和真实请求跟踪下评估了我们方案的性能。