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 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.
|Journal||Theoretical Computer Science|
Oommen, J, & Ng, D.T.H. (David T.H.). (1993). An optimal absorbing list organization strategy with constant memory requirements. Theoretical Computer Science, 119(2), 355–361. doi:10.1016/0304-3975(93)90166-Q