A Prediction Interval Search Scheme for the Move-to-the-Front Replacement Algorithm
P. R. NELSON · IMA Journal of Applied Mathematics · 1979
The problem of how to search a serial list for a particular item when searches are performed one at a time, each item is demanded with fixed probability independent of previous demands and replacement is always made at the top of the list, is examined. A prediction interval for the position of each item is constructed, and using these intervals a search scheme is presented having the property that the expected number of positions that must be searched to find the next book demanded is less than if searches always commence at the top of the list.