Publications
Detailed Information
A competitive online algorithm for the paging problem with "shelf" memory
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hong, Sung-Pil | - |
dc.date.accessioned | 2009-07-08T07:26:10Z | - |
dc.date.available | 2009-07-08T07:26:10Z | - |
dc.date.issued | 1999 | - |
dc.identifier.citation | Lecture Notes in Computer Science, Vol. 1627/1999 (1999) 400-408 | en |
dc.identifier.isbn | 978-3-540-66200-6 | - |
dc.identifier.issn | 0302-9743 (print) | - |
dc.identifier.issn | 1611-3349 (online) | - |
dc.identifier.uri | https://hdl.handle.net/10371/5337 | - |
dc.description.abstract | We consider an extension of the two-level paging problem.
Besides a fast memory (the cache) and a slow memory, we postulate a third memory, called the \shelf", near the fast memory so that it is more cost-e cient to store or retrieve a page from the shelf than to retrieve a page from the slow memory. Unlike the standard two-level paging prob- lem, the extension is not a special case of the K-server problem as it is not embedded in a space with a symmetric metric. Our goal is to establish an upper bound on the competitive ratio of this \three-level" memory paging problem. We show that unless per page storage costs more than per page retrieval from the shelf, a simple extension of the well-known LRU algorithm has competitive ratio of 2k + l + 1, where k and l are, respectively, the capacities of the cache and the shelf. If, in addition, k l, then the same algorithm is k + l + 2-competitive | en |
dc.description.sponsorship | The research is partially supported by Chung-Ang University Research Grant 96-106. | en |
dc.language.iso | en | - |
dc.publisher | Springer Verlag | en |
dc.relation.ispartofseries | Lecture Notes in Computer Science | en |
dc.relation.ispartofseries | Volume 1627/1999 | en |
dc.title | A competitive online algorithm for the paging problem with "shelf" memory | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.identifier.doi | 10.1007/3-540-48686-0_40 | - |
dc.identifier.doi | 10.1007/3-540-48686-0_40 | - |
dc.citation.journaltitle | Lecture Notes in Computer Science = LNCS | - |
- Appears in Collections:
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.