Optimal Prefetching in Random Trees - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Mathematics Année : 2021

Optimal Prefetching in Random Trees

Kausthub Keshava
  • Fonction : Auteur
  • PersonId : 1112013

Résumé

We propose and analyze a model for optimizing the prefetching of documents, in the situation where the connection between documents is discovered progressively. A random surfer moves along the edges of a random tree representing possible sequences of documents, which is known to a controller only up to depth d. A quantity k of documents can be prefetched between two movements. The question is to determine which nodes of the known tree should be prefetched so as to minimize the probability of the surfer moving to a node not prefetched. We analyzed the model with the tools of Markov decision process theory. We formally identified the optimal policy in several situations, and we identified it numerically in others.
Fichier principal
Vignette du fichier
mathematics-09-02437-v4.pdf (428.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03361953 , version 1 (01-10-2021)
hal-03361953 , version 2 (15-10-2021)

Licence

Paternité

Identifiants

Citer

Kausthub Keshava, Alain Jean-Marie, Sara Alouf. Optimal Prefetching in Random Trees. Mathematics , 2021, 9 (19), pp.2437. ⟨10.3390/math9192437⟩. ⟨hal-03361953v2⟩
67 Consultations
81 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More