TR-168: Adaptive List Organizing for Non-stationary Query Distributions. Part I: The Move-to-Front Rule

Abstract

Consider a linear list ‘R composed of all the records in the set { R1, R2, • • • , RN }. At a given instant, the records appear in one of the N! permutations of the N elements. It is well known that in order to arrive at the minimum average cost of accesses, the list ‘R, must be arranged in the decreasing order of probabilities of accessing the elements. Many heuristics to dynamically reorganize the list are known in the literature and include the Move-to-Front (MTF) and the Transposition (TR) rules.
The assumption made in all studies of adaptive linear lists has been that the access probability distribution is time invariant, and that the individual accesses are statistically independent. This paper studies the impact of relaxing the time invariance assumption. Two models of non-stationary query distributions are suggested in this paper. The first approach is based on the idea of switching environments [11] and the second model is completely general and allows the probability distribution vector itself to be a random vector.
The MTF rule is analyzed under both these models. The theoretical results presented in the paper have been experimentally validated.