TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies

Abstract

Let lt = {R1 ,R2, … , AN} be a list of elements in which Ai is accessed with an (unknown) probability Si. To minimize the cost of accessing the elements, it is advantageous if the elements are sorted in the descending order of the access probabilities. Attempts to achieve this have been made in which a simple list reordering operation is performed on every access.
In this paper we present two simple self-organizing strategies. The strategies are deterministic and absorbing in their Markovian representation and are completely counter-intuitive, in that they are of a Move-To-Rear (MTR) flavour. Whereas the first of the schemes requires linear space (space proportional to the number of elements in the list}, the second requires only constant space. We show that the former scheme is optimal, independent of the distribution of the access probabilities. By this we mean that although the list could converge to one of its N! configurations, by suitably performing the move-to-rear operation, the probability of converging to the right arrangement can be made as close to unity as desired. The second scheme requiring constant space is shown to be expedient. We conjecture its optimality.