Paging and list update under bijective analysis

ABSTRACT

It 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 from extremely naive and inefficient strategies (such as Flush-When-Full), to strategies of excellent performance in practice (such as Least-Recently-Used and some of its variants). A similar situation arises in the list update problem: in particular, under the cost formulation studied by Martínez and Roura [TCS 2000] and Munro [ESA 2000] every list update algorithm has, asymptotically, the same competitive ratio. Several refinements of competitive analysis, as well as alternative performance measures have been introduced in the literature, with varying degrees of success in narrowing this disconnect between theoretical analysis and empirical evaluation.

In this paper we study these two fundamental online problems under the framework of bijective analysis [Angelopoulos, Dorrigiv and López-Ortiz, SODA 2007 and LATIN 2008]. This is an intuitive technique which is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size. Coupled with a well-established model of locality of reference due to Albers, Favrholdt and Giel [JCSS 2005], we show that Least-Recently-Used and Move-to-Front are the unique optimal algorithms for paging and list update, respectively. Prior to this work, only measures based on average-cost analysis have separated LRU and MTF from all other algorithms. Given that bijective analysis is a fairly stringent measure (and also subsumes average-cost analysis), we prove that in a strong sense LRU and MTF stand out as the best algorithms.

REFERENCES

• 1: Susanne Albers , Lene M. Favrholdt , Oliver Giel, On paging with locality of reference, Journal of Computer and System Sciences, v.70 n.2, p.145-175, March 2005 [doi>10.1016/j.jcss.2004.08.002]
• 2: S. Albers and M. Mitzenmacher. Average case analyses of list update algorithms, with applications to data compression. Algorithmica, 21(3):312--329, 1998.
• 3: Spyros Angelopoulos , Reza Dorrigiv , Alejandro López-Ortiz, On the separation and equivalence of paging strategies, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.229-237, January 07-09, 2007, New Orleans, Louisiana
• 4: S. Angelopoulos, R. Dorrigiv, and A. López-Ortiz. List update with locality of reference. In Proceedings of the 8th Latin American Theoretical Informatics Symposium, pages 399--410, 2008.
• 5: L. Becchetti. Modeling locality: A probabilistic analysis of LRU and FWF. In Proceedings of the 12th European Symposium on Algorithms (ESA), pages 98--109, 2004.
• 6: S. Ben-David and A. Borodin. A new measure for the study of on-line algorithms. Algorithmica, 11(1):73--91, 1994.
• 7: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 8: Allan Borodin , Sandy Irani , Prabhakar Raghavan , Baruch Schieber, Competitive paging with locality of reference, Journal of Computer and System Sciences, v.50 n.2, p.244-258, April 1995
• 9: J. Boyar, M. R. Ehmsen, and K. S. Larsen. Theoretical evidence for the superiority of LRU-2 over LRU for the paging problem. In Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA), pages 95--107, 2006.
• 10: Joan Boyar , Lene M. Favrholdt , Kim S. Larsen, The relative worst-order ratio applied to paging, Journal of Computer and System Sciences, v.73 n.5, p.818-843, August, 2007 [doi>10.1016/j.jcss.2007.03.001]
• 11: J. Boyar, S. Irani, and K. S. Larsen. A comparison of performance measures for online algorithms, 2008. Available from arXiv.org, number 0806.0983v1.
• 12: Joan Boyar , Kim S. Larsen , Morten N. Nielsen, The Accommodating Function: A Generalization of the Competitive Ratio, SIAM Journal on Computing, v.31 n.1, p.233-258, 2001 [doi>10.1137/S0097539799361786]
• 13: M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report 124, DEC SRC, 1994.
• 14: M. Chrobak and J. Noga. LRU is better than FIFO. Algorithmica, 23(2):180--185, 1999.
• 15: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 16: R. Dorrigiv and A. López-Ortiz. A survey of performance measures for on-line algorithms. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 36(3):67--81, September 2005.
• 17: A. Fiat and G. J. Woeginger. Online Algorithms---The State of the Art, volume 1442 of LNCS. Springer-Verlag, 1998.
• 18: J. H. Hester , D. S. Hirschberg, Self-organizing linear search, ACM Computing Surveys (CSUR), v.17 n.3, p.295-311, Sept. 1985 [doi>10.1145/5505.5507]
• 19: Benjamin Hiller , Tjark Vredeveld, Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_44]
• 20: H. Kaplan, S. Landau, and E. Verbin. A simpler analysis of burrows-wheeler based compression. In Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching, pages 282--293, 2006.
• 21: A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 3:77--119, 1988.
• 22: Anna R. Karlin , Steven J. Phillips , Prabhakar Raghavan, Markov Paging, SIAM Journal on Computing, v.30 n.3, p.906-922, 2000 [doi>10.1137/S0097539794268042]
• 23: Claire Kenyon, Best-fit bin-packing with random order, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.359-364, January 28-30, 1996, Atlanta, Georgia, United States
• 24: Elias Koutsoupias , Christos H. Papadimitriou, Beyond Competitive Analysis, SIAM Journal on Computing, v.30 n.1, p.300-317, 2000 [doi>10.1137/S0097539796299540]
• 25: Conrado Martínez , Salvador Roura, On the competitiveness of the move-to-front rule, Theoretical Computer Science, v.242 n.1-2, p.313-325, July 6, 2000 [doi>10.1016/S0304-3975(98)00264-3]
• 26: J. Ian Munro, On the Competitiveness of Linear Search, Proceedings of the 8th Annual European Symposium on Algorithms, p.338-345, September 05-08, 2000
• 27: Konstantinos Panagiotou , Alexander Souza, On adequate performance measures for paging, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132587]
• 28: Frank Schulz, Two New Families of List Update Algorithms, Proceedings of the 9th International Symposium on Algorithms and Computation, p.99-108, December 14-16, 1998
• 29: Abraham Silberschatz , Peter Baer Galvin , Greg Gagne, Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 2001
• 30: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 31: E. Torng. A unified analysis of paging and caching. Algorithmica, 20(2):175--200, 1998.
• 32: I. H. Witten and T. Bell. The Calgary/Canterbury text compression corpus. Anonymous ftp from ftp://ftp.cpsc.ucalgary.ca/pub/projects/.
• 33: N. E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525--541, 1994.
• 34: Neal E. Young, Bounding the diffuse adversary, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.420-425, January 25-27, 1998, San Francisco, California, United States
• 35: Neal E. Young, On-line paging against adversarially biased random inputs, Journal of Algorithms, v.37 n.1, p.218-235, Oct. 2000 [doi>10.1006/jagm.2000.1099]
• 36: N. E. Young. On-line file caching. Algorithmica, 33(3):371--383, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation