Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2018) | last year (2017) | two years ago (2016) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Angelopoulos, Spyros
Dorrigiv, Reza
López-Ortiz, Alejandro

dblp
dblp
dblp

Not MPG Author(s):

Dorrigiv, Reza
López-Ortiz, Alejandro

Editor(s):





BibTeX cite key*:

Angelopoulos2007SODA2

Title, Booktitle

Title*:

On the separation and equivalence of paging strategies

Booktitle*:

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007

Event, URLs

URL of the conference:

http://www.siam.org/meetings/da07/

URL for downloading the paper:

http://portal.acm.org/citation.cfm?doid=1283383.1283408

Event Address*:

New Orleans, Louisiana, USA

Language:

English

Event Date*
(no longer used):


Organization:

Association for Computing Machinery (ACM), Society for Industrial and Applied Mathematics (SIAM)

Event Start Date:

7 January 2007

Event End Date:

9 January 2007

Publisher

Name*:

SIAM

URL:

http://www.siam.org

Address*:

Philadelphia, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

January

Pages:

229-237

Year*:

2007

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

It has been experimentally observed that LRU and variants thereof are the preferred strategies for on-line paging. However, under most proposed performance measures for on-line algorithms the performance of LRU is the same as that of many other strategies which are inferior in practice. In this paper we first show that any performance measure which does not include a partition or implied distribution of the input sequences of a given length is unlikely to distinguish between any two lazy paging algorithms as their performance is identical in a very strong sense. This provides a theoretical justification for the use of a more refined measure. Building upon the ideas of concave analysis by Albers et al. [AFG05], we prove strict separation between LRU and all other paging strategies. That is, we show that LRU is the unique optimum strategy for paging under a deterministic model. This provides full theoretical backing to the empirical observation that LRU is preferable in practice.

URL for the Abstract:

http://portal.acm.org/citation.cfm?doid=1283383.1283408

Keywords:

Online Algorithms, Paging

HyperLinks / References / URLs:

http://portal.acm.org/citation.cfm?doid=1283383.1283408



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Angelopoulos2007SODA2,
AUTHOR = {Angelopoulos, Spyros and Dorrigiv, Reza and L{\"o}pez-Ortiz, Alejandro},
TITLE = {On the separation and equivalence of paging strategies},
BOOKTITLE = {Proceedings of the Eighteenth Annual {ACM}-{SIAM} Symposium on Discrete Algorithms, {SODA} 2007},
PUBLISHER = {SIAM},
YEAR = {2007},
ORGANIZATION = {Association for Computing Machinery (ACM), Society for Industrial and Applied Mathematics (SIAM)},
PAGES = {229--237},
ADDRESS = {New Orleans, Louisiana, USA},
MONTH = {January},
}


Entry last modified by Spyros Angelopoulos, 03/20/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Spyros Angelopoulos
Created
01/18/2008 02:21:47 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Spyros Angelopoulos
Spyros Angelopoulos
Spyros Angelopoulos
Uwe Brahm
Uwe Brahm
Edit Dates
03/20/2009 04:02:00 PM
02/16/2009 11:19:18 AM
02/16/2009 11:18:59 AM
01/20/2009 07:10:17 PM
06.03.2008 14:27:14
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section