Relative Interval Analysis of Paging Algorithms on Access Graphs

Joan Boyar; Sushmita Gupta; Kim Skak Larsen

doi:10.1007/978-3-642-40104-6_17

Relative Interval Analysis of Paging Algorithms on Access Graphs

Joan Boyar, Sushmita Gupta, Kim Skak Larsen

Department of Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the expected results are obtained. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from [Dorrigiv, López-Ortiz, Munro, 2009], obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis.

Original language	English
Title of host publication	Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Volume	8037
Publisher	Springer
Publication date	2013
Pages	195-206
ISBN (Print)	978-3-642-40103-9
DOIs	https://doi.org/10.1007/978-3-642-40104-6_17
Publication status	Published - 2013
Event	Algorithms & Data Structures Symposium - University of Western Ontario, London, Ontario, Canada Duration: 12. Aug 2013 → 14. Aug 2013

Conference

Conference	Algorithms & Data Structures Symposium
Location	University of Western Ontario
Country/Territory	Canada
City	London, Ontario
Period	12/08/2013 → 14/08/2013

Series	Lecture Notes in Computer Science
ISSN	0302-9743

Documents & Links

10.1007/978-3-642-40104-6_17

Algorithms & Data Structures Symposium
Joan Boyar (Participant)
11. Aug 2013 → 14. Aug 2013
Activity: Attending an event › Organisation or participation in workshops, courses or seminars

Cite this

@inproceedings{b7cc95fdbfeb47918180dfecf6dff81b,

title = "Relative Interval Analysis of Paging Algorithms on Access Graphs",

abstract = "Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the expected results are obtained. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from [Dorrigiv, L{\'o}pez-Ortiz, Munro, 2009], obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis.",

keywords = "online algorithms, paging, relative interval analysis, access graphs",

author = "Joan Boyar and Sushmita Gupta and Larsen, {Kim Skak}",

year = "2013",

doi = "10.1007/978-3-642-40104-6_17",

language = "English",

isbn = "978-3-642-40103-9",

volume = "8037",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "195--206",

booktitle = "Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings",

address = "Germany",

note = "Algorithms & Data Structures Symposium ; Conference date: 12-08-2013 Through 14-08-2013",

}

Boyar, J, Gupta, S & Larsen, KS 2013, Relative Interval Analysis of Paging Algorithms on Access Graphs. in Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. vol. 8037, Springer, Lecture Notes in Computer Science, pp. 195-206, Algorithms & Data Structures Symposium, London, Ontario, Canada, 12/08/2013. https://doi.org/10.1007/978-3-642-40104-6_17

Relative Interval Analysis of Paging Algorithms on Access Graphs. / Boyar, Joan; Gupta, Sushmita; Larsen, Kim Skak.

Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. Vol. 8037 Springer, 2013. p. 195-206 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Relative Interval Analysis of Paging Algorithms on Access Graphs

AU - Boyar, Joan

AU - Gupta, Sushmita

AU - Larsen, Kim Skak

PY - 2013

Y1 - 2013

N2 - Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the expected results are obtained. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from [Dorrigiv, López-Ortiz, Munro, 2009], obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis.

AB - Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the expected results are obtained. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from [Dorrigiv, López-Ortiz, Munro, 2009], obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis.

KW - online algorithms

KW - paging

KW - relative interval analysis

KW - access graphs

U2 - 10.1007/978-3-642-40104-6_17

DO - 10.1007/978-3-642-40104-6_17

M3 - Article in proceedings

SN - 978-3-642-40103-9

VL - 8037

T3 - Lecture Notes in Computer Science

SP - 195

EP - 206

BT - Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings

PB - Springer

T2 - Algorithms & Data Structures Symposium

Y2 - 12 August 2013 through 14 August 2013

ER -

Relative Interval Analysis of Paging Algorithms on Access Graphs

Abstract

Conference

Documents & Links

Fingerprint

Related Activities

Algorithms & Data Structures Symposium

Cite this