Skip to Main content Skip to Navigation
New interface
Journal articles

Optimal Prefetching in Random Trees

Kausthub Keshava 1 Alain Jean-Marie 2, * Sara Alouf 2, 3 
* Corresponding author
2 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-03361953
Contributor : Sara Alouf Connect in order to contact the contributor
Submitted on : Friday, October 15, 2021 - 2:13:50 PM
Last modification on : Friday, November 4, 2022 - 3:02:51 PM

File

mathematics-09-02437-v4.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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

Share

Metrics

Record views

55

Files downloads

69