TTL Model for an LRU-Based Similarity Caching Policy

# 177





Abstract

Similarity caching allows requests for an item to be served by a similar item. Applications include recommendation systems, multimedia retrieval, and machine learning. Recently, many similarity caching policies have been proposed, like SIM-LRU and its generalization RND-LRU, but the performance analysis of their hit ratio is still wanting. In this talk, we show how to extend the popular time-to-live approximation in classic caching to similarity caching. In particular, we propose a method to estimate the hit ratio of the similarity caching policy RND-LRU. Our method, the RND-TTL approximation, introduces the RND-TTL cache model and then tunes its parameters in such a way as to mimic the behavior of RND-LRU. The parameter tuning involves solving a fixed point system of equations for which we provide an algorithm for numerical resolution and sufficient conditions for its convergence. Our approach for approximating the hit ratio of RND-LRU is evaluated on both synthetic and real-world traces.

Dr. Sara Alouf, INRIA

Sara Alouf is a Researcher at Inria and vice-head of the Network Engineering and Operations group. Prior to joining Inria in March 2004, she held a post-doctoral position at Vrije Universiteit, Amsterdam, within the Optimization of Business Processes group. She received her Habilitation in 2017 from the Université Côte d'Azur, her Ph.D. and M.Sc. from the Université Nice Sophia Antipolis in 2002 and 1999, respectively. She holds an Electrical and Electronics Engineering Degree from the Lebanese University, obtained in 1998. While at Inria, She has been involved in the common labs between Inria and Alcatel-Lucent (now Nokia) and between Inria and Alstom Transport. She was in the board of directors of ACM Sigmetrics (July 2019 - June 2023) and serve/served in the technical program committees of ACM Sigmetrics and MobiHoc, Performance, IEEE Infocom and Globecom, ITC, Valuetools, and WIOPT. She was the general co-chair of the ACM Sigmetrics/IFIP Performance 2016 conference. She is a member of the ACM and ACM Sigmetrics and serves as Area Editor for Elsevier Computer Communications. Her research interests include stochastic modeling and performance evaluation of communication networks.