Optimal Prefetching in Random Trees

Kausthub Keshava, Alain Jean-Marie and Sara Alouf
Additional contact information
Kausthub Keshava: Deloitte India (Offices of the US), Hyderabad 500032, Telangana, India
Alain Jean-Marie: Inria, University of Montpellier, 34095 Montpellier, France
Sara Alouf: Inria, Université Côte d’Azur, 06902 Sophia Antipolis, France

Mathematics, 2021, vol. 9, issue 19, 1-26

Abstract: 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.

Keywords: prefetching; optimization; Markov decision processes; random trees; Galton–Watson (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/19/2437/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/19/2437/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:19:p:2437-:d:648134

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().