On list update with locality of reference

Susanne Albers, Sonja Lauer

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We present a comprehensive study of the list update problem with locality of reference. More specifically, we present a combined theoretical and experimental study in which the theoretically proven and experimentally observed performance guarantees of algorithms match or nearly match. Firstly, we introduce a new model of locality of reference that closely captures the concept of runs. Using this model we develop refined theoretical analyses of popular list update algorithms. Secondly, we present an extensive experimental study in which we have tested the algorithms on traces from benchmark libraries. The theoretical and experimental bounds differ by just a few percent. Our new theoretical bounds are substantially lower than those provided by standard competitive analysis. It shows that the well-known Move-To-Front strategy exhibits the best performance. Its refined competitive ratio tends to 1 as the degree of locality increases. This confirms that Move-To-Front is the method of choice in practice.

Original languageEnglish
Pages (from-to)627-653
Number of pages27
JournalJournal of Computer and System Sciences
Volume82
Issue number5
DOIs
StatePublished - 1 Aug 2016

Keywords

  • Competitive analysis
  • Data structures
  • Locality of reference
  • Online algorithms
  • Self-organizing lists

Fingerprint

Dive into the research topics of 'On list update with locality of reference'. Together they form a unique fingerprint.

Cite this