A New Perspective on List Update: Probabilistic Locality and Working Set
[.pdf]
Abstract
In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that MTF is the best list update algorithm under any such distribution.
Furthermore, we study the working set property of online list update algorithms.
The working set property indicates the good performance of an online algorithm on sequences with locality of reference.
We show that no list update algorithm has the working set property.
Nevertheless, we can distinguish among list update algorithms by comparing their performance in terms of the working set bound.
We prove bounds for several well known list update algorithms and conclude that MTF attains the best performance in this context as well.
Bibtex Entry
