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

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstrakt

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
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	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

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

Algorithms & Data Structures Symposium
Joan Boyar (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",

address = "Germany",

note = "null ; 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. 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. 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

PB - Springer

Y2 - 12 August 2013 through 14 August 2013

ER -

Relative Interval Analysis of Paging Algorithms on Access Graphs

Abstrakt

Konference

Emneord

Dokumenter og links

Relaterede Aktiviteter

Algorithms & Data Structures Symposium

Citationsformater