TR-154: Ideal List Organization for Stationary Environments

Abstract

We consider the problem of adaptively organizing a list whose elements are accessed with a fixed but unknown probability distribution. We present a strategy which has constant additional space requirements and which achieves the reorganization by performing a data restructuring operation on an element exactly once. The scheme, which is stochastically absorbing, and is of a Move-to-Rear flavour is shown to be asymptotically optimal. In other words, by suitably performing the Move-to-Rear operation the probability of converging to the optimal arrangement can be made as close to unity as desired. Considering all of these features, this strategy is probably the most ideal list organization strategy reported in the literature. Simulation results demonstrating the power of the scheme have been included. The paper also includes a hybrid data reorganization scheme in which an absorbing Move-To-Rear rule and an ergodic rule are used L’l conjunction with each other to optimize the data retrieval process.