Amortized efficiency of list update and paging rules

ABSTRACT

In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes &thgr;(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.

REFERENCES

• 1: Andqrson, E.J., Nash, I'.. and Weber, R.R. A counterexample to a conjecture on optimal list ordering. {. Appl. Prob.. to appear.
• 2: Belady, L.A. A study of replacement algorithms for virtual storage computers. IBM Syst. J 5 (19&j), 78-101.
• 3: Bentley, J.L., and McCeoch, C. Worst-case analysis of self-organizing seouential search heuristics. In Proceedings of 2Ofh Allerton Confcrence on Communication, Control, and Cornfifing, (Univ. Illinois, Urbana-Champaign. Oct. 6-8,1962), 1983.45~461.
• 4: Bitner. J.R. Heuristics that dynamically organize data structures. SIAMJ. Comput. 8 (1979). 82-110.
• 5: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 6: P. A. Franaszek , T. J. Wagner, Some Distribution-Free Aspects of Paging Algorithm Performance, Journal of the ACM (JACM), v.21 n.1, p.31-39, Jan. 1974 [doi>10.1145/321796.321800]
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
• 9: Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977

INDEX TERMS

Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Swapping**

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues; Tables**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Performance, Theory, Verification