TR-76: List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations

Abstract

Consider a list of elements {R , … ,RN} in which the element Ri is accessed with an (unknown) probability si. If the cost of accessing R i is proportional to i (as in sequently search) then
it is advantageous if each access is accompanied by a simple reordering operation. Th is operation is ch osen so that ultimately the list will be sorted in the descending order of the access probabilities.
In this paper we present two list organizing schemes — the first of which uses bounded memory and the second which uses memory proportional to number of elements in the list. Both of the schemes reorder the list by moving only the accessed element. However, as opposed to the schemes discussed in the literature the move operation is performed stochastically in such a way that ultimately no more move operations are performed. When this occurs we say that the scheme has converged. We shall show that: