Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427705 | Information Processing Letters | 2012 | 4 Pages |
Abstract
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.
► We introduce a probabilistic model for list update with locality of reference. ► This model is based on the diffuse adversary model. ► We prove that MTF outperforms other algorithms in this model.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Reza Dorrigiv, Alejandro López-Ortiz,