论文标题
计算相似性缓存的命中率
Computing the Hit Rate of Similarity Caching
论文作者
论文摘要
相似性缓存允许请求项目\（i \）由类似的项目\（i'\）提供。应用程序包括建议系统，多媒体检索和机器学习。最近，已经提出了许多相似性缓存策略，但是即使对于最简单的策略，我们仍然不知道如何计算命中率，例如SIM-LRU和RND-LRU，它们是经典的缓存算法的直接修改。本文提出了第一种算法来计算请求过程独立参考模型下的相似性缓存策略的命中率。特别是，我们的工作显示了如何将流行的TTL近似值从经典缓存扩展到相似性缓存。该算法对合成和现实世界的痕迹进行评估。
Similarity caching allows requests for an item \(i\) to be served by a similar item \(i'\). Applications include recommendation systems, multimedia retrieval, and machine learning. Recently, many similarity caching policies have been proposed, but still we do not know how to compute the hit rate even for the simplest policies, like SIM-LRU and RND-LRU that are straightforward modifications of classical caching algorithms. This paper proposes the first algorithm to compute the hit rate of similarity caching policies under the independent reference model for the request process. In particular, our work shows how to extend the popular TTL approximation from classic caching to similarity caching. The algorithm is evaluated on both synthetic and real world traces.
