Daniel D. Sleator
Robert E. Tarjan
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 θ(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.
- 1 Andqrson, E.J., Nash, I'. and Weber, R.R. A counterexample to a conjecture on optimal list ordering. {. Appl. Prob. to appear.Google Scholar
- 2 Belady, L.A. A study of replacement algorithms for virtual storage computers. IBM Syst. J 5 (19&j), 78-101.Google Scholar
- 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.Google Scholar
- 4 Bitner. J.R. Heuristics that dynamically organize data structures. SIAMJ. Comput. 8 (1979). 82-110.Google Scholar
- 5 Coffman. E.G. and Denning, P.J. Operating Systems Theorlj, Prentice- Hall, Englewood Cliffs, NJ, 1973. Google ScholarDigital Library
- 6 Franaszek, P.A. and Wagner, T.J. Some distribution-free aspects of paging performance. J. ACM 21, 1 (Jan. 1974), 31-39. Google ScholarDigital Library
- 7 Knuth. DE. The Art of Computer Programming, Volume 3: Sorting and Searching Addison-Wesley, Reading, MA, 1973. Google ScholarDigital Library
- 8 Rivest. R. On self-organizing sequential search heuristics. Commun. ACM 19, 2 {Feb. 1976), 63-67. Google ScholarDigital Library
- 9 Spirn, J.R. Progam Behavior: Models and Measurements. Elsevier, New York. 1977. Google ScholarDigital Library
Index Terms
- Amortized efficiency of list update and paging rules
Recommendations
Parameterized Analysis of Paging and List Update Algorithms
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 ...
List update with locality of reference
LATIN'08: Proceedings of the 8th Latin American conference on Theoretical informaticsIt is known that in practice, request sequences for the list update problem exhibit a certain degree of locality of reference. Motivated by this observation we apply the locality of reference model for the paging problem due to Albers et al. [STOC 2002/...
Paging and list update under bijective analysis
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithmsIt has long been known that for the paging problem in its standard form, competitive analysis cannot adequately distinguish algorithms based on their performance: there exists a vast class of algorithms which achieve the same competitive ratio, ranging ...
Reviews
Charles N. Schroeder
.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 offline paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No existing on-line paging algorithm has better amortized performance. — Authors' Abstract The above abstract gives a good overview of the content of the paper. The paper is interesting; however, a knowledge of list organization and manipulation is necessary to be able to follow the discussion. The concepts presented and the proofs of theorems would be difficult for a novice to follow or comprehend.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments