In papers about self-organizing data structures, it is often mentioned that the assumption of independence of successive requests of keys should be relaxed and that the dependence should assume the form of a locality phenomenon. In this setting, the move-to-front rule is considered to be of interest, but no optimality result concerning this rule has yet appeared. In this paper we assume that the sequence of required keys is a Markov chain with a transition kernel $P$ and we consider the class $\mathscr{F}^\ast$ of stochastic matrices $P$ such that move-to-front is optimal among on-line rules, with respect to the stationary search cost. We give properties of $\mathscr{F}^\ast$ that bear out the usual explanation of optimality of move-to-front by a locality phenomenon exhibited by the sequence of required keys. We explicitly produce a large subclass of $\mathscr{F}^\ast$, while showing that in some cases move-to-front is optimal with respect to the speed of convergence toward stationary search cost.
Publié le : 1993-11-14
Classification:
Controlled Markov chain,
Bellman optimality condition,
self-organizing data structure,
sequential search,
locality,
68P05,
90C40,
60J10
@article{1177005280,
author = {Chassaing, Philippe},
title = {Optimality of Move-to-Front for Self-Organizing Data Structures with Locality of References},
journal = {Ann. Appl. Probab.},
volume = {3},
number = {4},
year = {1993},
pages = { 1219-1240},
language = {en},
url = {http://dml.mathdoc.fr/item/1177005280}
}
Chassaing, Philippe. Optimality of Move-to-Front for Self-Organizing Data Structures with Locality of References. Ann. Appl. Probab., Tome 3 (1993) no. 4, pp. 1219-1240. http://gdmltest.u-ga.fr/item/1177005280/