Parameterized Analysis of Paging and List Update Algorithms

Paging and list update are two classical online problems. Standard competitive analysis often gives very pessimistic results, compared to practical algorithms performance, especially for the paging problem. The source of the problem is that request sequences arising in practice exhibit locality of reference, which is not captured by standard competitiveness. For the paging problem, many studies have been presented that integrate the concept of locality, culminating with the LRU separation results in SODA'07 (with Angelopoulos and Dorrigiv) and in SODA'09 earlier this year by Angelopoulos and Schweitzer. These separation results are based on heavy machinery specifically designed to resolve this singular long-standing question.

In this talk we present a related model of locality based on inter-request distance which captures most of the benefits of the previous model. The new measure is easier to apply and creates a performance hierarchy of paging and list update algorithms which better reflects their intuitive relative strengths. Several previously observed experimental properties can be readily proven using the new model.