An optimal absorbing list organization strategy with constant memory requirements

AbstractWe consider the problem of adaptively organizing a list whose elements are accessed with a fixed but unknown probability distribution. We present an absorbing scheme requiring constant additional space which reorganizes the list by performing a restructuring operation on an element exactly once. The scheme is asymptotically optimal. We also describe a hybrid reorganization scheme in which the absorbing rule and an ergodic rule are used in conjunction with each other to enhance the transient data retrieval process