Optimality of Move-to-Front for Self-Organizing Data Structures with Locality of References

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 F. 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 F. 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 F., while showing that in some cases move-to-front is optimal with respect to the speed of convergence toward stationary search cost.