AN OPTIMAL ABSORBING LIST ORGANIZATION STRATEGY WITH CONSTANT MEMORY REQUIREMENTS

We consider the problem of adaptively organizing a list whose elements are accessed with a fixed but unknown probability distribution. We pr esent an absorbing scheme requiring constant additional space which re organizes the list by performing a restructuring operation on an eleme nt exactly once. The scheme is asymptotically optimal. We also describ e a hybrid reorganization scheme in which the absorbing rule and an er godic rule are used in conjunction with each other to enhance the tran sient data retrieval process.