06059704

j

06059704 Dorrigiv, Reza L\'opez-Ortiz, Alejandro List update with probabilistic locality of reference. Inf. Process. Lett. 112, No. 13, 540-543 (2012). 2012 Elsevier Sciences Publishers (North-Holland), Amsterdam EN on-line algorithms analysis of algorithms data structures list update locality of reference

doi:10.1016/j.ipl.2012.04.002

Summary: 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.