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

Institut for Matematik og Datalogi

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Vol/bind	8037
Forlag	Springer
Publikationsdato	2013
Sider	195-206
ISBN (Trykt)	978-3-642-40103-9
DOI	https://doi.org/10.1007/978-3-642-40104-6_17
Status	Udgivet - 2013
Begivenhed	Algorithms & Data Structures Symposium - University of Western Ontario, London, Ontario, Canada Varighed: 12. aug. 2013 → 14. aug. 2013

Konference

Konference	Algorithms & Data Structures Symposium
Lokation	University of Western Ontario
Land/Område	Canada
By	London, Ontario
Periode	12/08/2013 → 14/08/2013

Navn	Lecture Notes in Computer Science
ISSN	0302-9743

Emneord

online algorithms
paging
relative interval analysis
access graphs

Dokumenter og links

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

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

1 Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

Algorithms & Data Structures Symposium
Boyar, J. (Deltager)
11. aug. 2013 → 14. aug. 2013
Aktivitet: Deltagelse i faglig begivenhed › Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

Citationsformater

@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. i Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. bind 8037, Springer, Lecture Notes in Computer Science, s. 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. Bind 8037 Springer, 2013. s. 195-206 (Lecture Notes in Computer Science).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Dokumenter og links

SDU link

Fingeraftryk

Relaterede aktiviteter

Algorithms & Data Structures Symposium

Citationsformater