Computing the Hit Rate of Similarity Caching
Younes Ben Mazziane, Sara Alouf, Giovanni Neglia, Daniel Sadoc Menasché · GLOBECOM 2022 - 2022 IEEE Global Communications Conference · 2022
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 simple policies, like SIM-LRU and RND-LRU that are straightforward modifications of classic 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, we show how to extend the popular time-to-live approximation in classic caching to similarity caching. The algorithm is evaluated on both synthetic and real world traces.