MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.siam.org/meetings/da07/
Downloading URL:
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
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