List update with probabilistic locality of reference
In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality. (C) 2012 Published by Elsevier B.V.
list update locality of reference on-line algorithms analysis of algorithms data structures