Bj. Oommen et Dth. Ng, AN OPTIMAL ABSORBING LIST ORGANIZATION STRATEGY WITH CONSTANT MEMORY REQUIREMENTS, Theoretical computer science, 119(2), 1993, pp. 355-361
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.