Parameterized Analysis of Paging and List Update Algorithms
[.pdf]
Abstract
It is well-established that input sequences for paging and list update have locality of reference.
In this paper we analyze the performance of algorithms for these problems in terms of the amount of locality in the input sequence.
We define a measure for locality that is based on Denning's working set model and express the performance of well known algorithms in term of this parameter.
This introduces parameterized-style analysis to online algorithms.
The idea is to rather than normalizing the performance of an online algorithm by an (optimal) offline algorithm, we explicitly express the behavior of the algorithm in terms of two more natural parameters: the size of the cache and Denning's working set measure.
This technique creates a performance hierarchy of paging algorithms which better reflects their intuitive relative strengths.
Also it reflects the intuition that a larger cache leads to a better performance.
We obtain similar separation for list update algorithms.
Lastly, we show that, surprisingly, certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results.
Bibtex Entry
