List update with probabilistic locality of reference

作者：Dorrigiv Reza^*; Lopez Ortiz Alejandro

来源：Information Processing Letters, 2012, 112(13): 540-543.

DOI：10.1016/j.ipl.2012.04.002

• On-line algorithms
• Analysis of algorithms
• Data structures
• List update
• 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.

• 出版日期2012-7-15