Probabilistic analysis for caching

Analyse probabiliste pour le caching Les caches sont de petites mémoires qui accélèrent la récupération des données. L'un des objectifs des politiques de mise en cache est de sélectionner le contenu du cache afin de minimiser le temps de réponse aux requêtes d'objets. Un problème plus général permet de répondre approximativement à la requête d'un objet par un objet similaire mis en cache. Ce concept, appelé "mise en cache par similarité", s'avère utile pour les systèmes de recommandation. L'objectif est de minimiser le temps de latence tout en fournissant des réponses satisfaisantes. La compréhension théorique des algorithmes de gestion de la mémoire cache, sous des hypothèses spécifiques sur les requêtes, aide à choisir un algorithme approprié. Les politiques d'éviction du cache les plus répandues sont celles de l'utilisation la moins fréquente (LFU) et de l'utilisation la moins récente (LRU). LFU est efficace lorsque le processus requêtes est stationnaire, et LRU s'adapte aux changements dans les processus de requêtes. Les algorithmes d'apprentissage séquentiel, tels que l'algorithme aléatoire Follow-the-Perturbed Leader (FPL), appliqués à la mise en cache, bénéficient de garanties théoriques même dans le pire des cas.LFU et FPL s'appuient sur le nombre de requêtes d'objets. Cependant, le comptage est un défi dans les scénarios à mémoire limitée. Pour y remédier, les politiques de mise en cache utilisent des schémas de comptage approximatifs, tels que la structure de données Count-Min Sketch avec mises à jour conservatrices (CMS-CU), afin d'équilibrer la précision des comptages et l'utilisation de la mémoire. Dans le cadre de la mise en cache par similarité, RND-LRU est une stratégie LRU modifiée. Malheureusement, il reste difficile de quantifier théoriquement à la fois la performance d'un cache LFU utilisant CMS-CU, celle d'un cache FPL avec un algorithme de comptage approximatif, ainsi que celle de RND-LRU.Cette thèse explore trois algorithmes probabilistes : CMS-CU, FPL avec des estimations bruitées des nombres de requêtes d'objets (NFPL) et RND-LRU. Pour CMS-CU, nous proposons une approche novatrice pour trouver de nouvelles bornes supérieures sur l'espérance et le complémentaire de la fonction de répartition de l'erreur d'estimation sous un processus de requêtes i.i.d. De plus, nous démontrons que NFPL se comporte aussi bien que la politique de mise en cache statique, optimale et omnisciente, quelle que soit la séquence de requêtes (sous certaines conditions sur les comptages bruités). Enfin, nous introduisons une nouvelle politique de mise en cache qui est analytiquement résoluble. Nous montrons alors que cette politique approxime RND-LRU.