Abstract
Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs which grow with the length of the sequences.
Partially supported by the Danish Council for Independent Research.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albers, S., von Stengel, B., Werchner, R.: A combined BIT and TIMESTAMP algorithm for the list update problem. Inform. Proc. Letters 56, 135–139 (1995)
Albers, S., Westbrook, J.: Self-Organizing Data Structures. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol. 1442, pp. 13–51. Springer, Heidelberg (1998)
Bentley, J.L., McGeoch, C.C.: Amortized analyses of self-organizing sequential search heuristics. Comm. ACM 28, 404–411 (1985)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)
Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. Journal of Computer and System Sciences 50(2), 244–258 (1995)
Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. ACM Transactions on Algorithms 3(2), article no. 22 (2007)
Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst order ratio applied to paging. Journal of Computer and System Sciences 73(5), 818–843 (2007)
Boyar, J., Gupta, S., Larsen, K.S.: Access graphs results for LRU versus FIFO under relative worst order analysis, arXiv:1204.4047v1 [cs.DS] (2012)
Chrobak, M., Noga, J.: LRU is better than FIFO. Algorithmica 23(2), 180–185 (1999)
Denning, P.J.: The working set model for program behaviour. Comm. ACM 11(5), 323–333 (1968)
Denning, P.J.: Working sets past and present. IEEE Transactions on Software Engineering 6(1), 64–84 (1980)
Dorrigiv, R., López-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News 36(3), 67–81 (2005)
Ehmsen, M.R., Kohrt, J.S., Larsen, K.S.: List Factoring and Relative Worst Order Analysis. In: Jansen, K., Solis-Oba, R. (eds.) WAOA 2010. LNCS, vol. 6534, pp. 118–129. Springer, Heidelberg (2011)
Fiat, A., Karlin, A.R.: Randomized and multipointer paging with locality of reference. In: 27th Annual ACM Symposium on Theory of Computing, pp. 626–634 (1995)
Fiat, A., Mendel, M.: Truly online paging with locality of reference. In: 38th Annual Symposium on Foundations of Computer Science, pp. 326–335 (1997), extended version: CoRR, abs/cs/0601127 (2006)
Fiat, A., Rosen, Z.: Experimental studies of access graph based heuristics: Beating the LRU standard? In: 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 63–72 (1997)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Systems Tech. Journal 45(9), 1563–1581 (1966)
Irani, S., Karlin, A.R., Phillips, S.: Strongly competitive algorithms for paging with locality of reference. SIAM J. Comput. 25(3), 477–497 (1996)
Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. Journal of the ACM 47(4), 617–643 (2000)
Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3, 79–119 (1988)
Karlin, A.R., Phillips, S.J., Raghavan, P.: Markov paging. SIAM J. Comput. 30(3), 906–922 (2000)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Comm. ACM 28(2), 202–208 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boyar, J., Gupta, S., Larsen, K.S. (2012). Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis. In: Fomin, F.V., Kaski, P. (eds) Algorithm Theory – SWAT 2012. SWAT 2012. Lecture Notes in Computer Science, vol 7357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31155-0_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-31155-0_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31154-3
Online ISBN: 978-3-642-31155-0
eBook Packages: Computer ScienceComputer Science (R0)