View in EDS PDF Full Text

Paging with Request Sets.

Saved in:
Bibliographic Details
Title: Paging with Request Sets.
Authors: Epstein, Leah1 lea@math.haifa.ac.il, Stee, Rob2 vanstee@ira.uka.de, Tamir, Tami3 tami@idc.ac.il
Source: Theory of Computing Systems. Jan2009, Vol. 44 Issue 1, p67-81. 15p.
Subjects: Paging (Computer science), Online algorithms, Online data processing, Algorithms, NP-complete problems, Computational complexity
Abstract: A generalized paging problem is considered. Each request is expressed as a set of u pages. In order to satisfy the request, at least one of these pages must be in the cache. Therefore, on a page fault, the algorithm must load into the cache at least one page out of the u pages given in the request. The problem arises in systems in which requests can be serviced by various utilities (e.g., a request for a data that lies in various web-pages) and a single utility can service many requests (e.g., a web-page containing various data). The server has the freedom to select the utility that will service the next request and hopefully additional requests in the future. The case u=1 is simply the classical paging problem, which is known to be polynomially solvable. We show that for any u>1 the offline problem is NP-hard and hard to approximate if the cache size k is part of the input, but solvable in polynomial time for constant values of k. We consider mainly online algorithms, and design competitive algorithms for arbitrary values of k, u. We study in more detail the cases where u and k are small. We also give an algorithm which uses resource augmentation and which is asymptotically optimal for u=2. [ABSTRACT FROM AUTHOR]
Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 35820272
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Paging with Request Sets.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Epstein%2C+Leah%22">Epstein, Leah</searchLink><relatesTo>1</relatesTo><i> lea@math.haifa.ac.il</i><br /><searchLink fieldCode="AR" term="%22Stee%2C+Rob%22">Stee, Rob</searchLink><relatesTo>2</relatesTo><i> vanstee@ira.uka.de</i><br /><searchLink fieldCode="AR" term="%22Tamir%2C+Tami%22">Tamir, Tami</searchLink><relatesTo>3</relatesTo><i> tami@idc.ac.il</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Jan2009, Vol. 44 Issue 1, p67-81. 15p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Paging+%28Computer+science%29%22">Paging (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Online+algorithms%22">Online algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Online+data+processing%22">Online data processing</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22NP-complete+problems%22">NP-complete problems</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: A generalized paging problem is considered. Each request is expressed as a set of u pages. In order to satisfy the request, at least one of these pages must be in the cache. Therefore, on a page fault, the algorithm must load into the cache at least one page out of the u pages given in the request. The problem arises in systems in which requests can be serviced by various utilities (e.g., a request for a data that lies in various web-pages) and a single utility can service many requests (e.g., a web-page containing various data). The server has the freedom to select the utility that will service the next request and hopefully additional requests in the future. The case u=1 is simply the classical paging problem, which is known to be polynomially solvable. We show that for any u>1 the offline problem is NP-hard and hard to approximate if the cache size k is part of the input, but solvable in polynomial time for constant values of k. We consider mainly online algorithms, and design competitive algorithms for arbitrary values of k, u. We study in more detail the cases where u and k are small. We also give an algorithm which uses resource augmentation and which is asymptotically optimal for u=2. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=35820272
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00224-007-9029-2
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 15
        StartPage: 67
    Subjects:
      – SubjectFull: Paging (Computer science)
        Type: general
      – SubjectFull: Online algorithms
        Type: general
      – SubjectFull: Online data processing
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: NP-complete problems
        Type: general
      – SubjectFull: Computational complexity
        Type: general
    Titles:
      – TitleFull: Paging with Request Sets.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Epstein, Leah
      – PersonEntity:
          Name:
            NameFull: Stee, Rob
      – PersonEntity:
          Name:
            NameFull: Tamir, Tami
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan2009
              Type: published
              Y: 2009
          Identifiers:
            – Type: issn-print
              Value: 14324350
          Numbering:
            – Type: volume
              Value: 44
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Theory of Computing Systems
              Type: main
ResultId 1