Relative interval analysis of paging algorithms on access graphs
作者： Joan Boyar , Sushmita Gupta , Kim S. Larsen
DOI: 10.1016/J.TCS.2014.11.035
关键词: Locality of reference 、 Star (graph theory) 、 Computer science 、 Graph 、 Paging 、 Competitive analysis 、 Online algorithm 、 Indifference graph 、 FIFO (computing and electronics) 、 Algorithm 、 Interval arithmetic
摘要: Access graphs, which have been used previously in connection to competitive analysis and relative worst order model locality of reference paging, are considered with interval analysis. The algorithms LRU, FIFO, FWF, FAR compared using the path, star, cycle access graphs. In this model, some results obtained not surprising. However, although LRU is found be strictly better than FIFO on paths, it has worse performance stars, cycles, complete model. We solve an open question from Dorrigiv et al. (2009) 13], obtaining tight bounds relationship between
core.ac.uk
elsevier.com
sci-hub.se 参考文章(26)
Joan Boyar, Sushmita Gupta, Kim S. Larsen, Access graphs results for LRU versus FIFO under relative worst order analysis scandinavian workshop on algorithm theory. ,vol. 7357, pp. 328- 339 ,(2012) , 10.1007/978-3-642-31155-0_29
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
Joan Boyar, Sandy Irani, Kim S. Larsen, A Comparison of Performance Measures for Online Algorithms workshop on algorithms and data structures. pp. 119- 130 ,(2009) , 10.1007/978-3-642-03367-4_11
Susanne Albers, Lene M. Favrholdt, Oliver Giel, On paging with locality of reference Journal of Computer and System Sciences. ,vol. 70, pp. 145- 175 ,(2005) , 10.1016/J.JCSS.2004.08.002
Alejandro López-Ortiz, Reza Dorrigiv, Spyros Angelopoulos, On the separation and equivalence of paging strategies symposium on discrete algorithms. pp. 229- 237 ,(2007) , 10.5555/1283383.1283408
Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel D. Sleator, Competitive snoopy caching Algorithmica. ,vol. 3, pp. 79- 119 ,(1988) , 10.1007/BF01762111
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, The relative worst-order ratio applied to paging Journal of Computer and System Sciences. ,vol. 73, pp. 818- 843 ,(2007) , 10.1016/J.JCSS.2007.03.001
Daniel D. Sleator, Robert E. Tarjan, Amortized efficiency of list update and paging rules Communications of The ACM. ,vol. 28, pp. 202- 208 ,(1985) , 10.1145/2786.2793
Neal E. Young, The k -server dual and loose competitiveness for paging Algorithmica. ,vol. 11, pp. 525- 541 ,(1994) , 10.1007/BF01189992
E. Torng, A Unified Analysis of Paging and Caching Algorithmica. ,vol. 20, pp. 175- 200 ,(1998) , 10.1007/PL00009192