Paging with Succinct Predictions Article Swipe
Antonios P. Antoniadis
,
Joan Boyar
,
Marek Eliáš
,
Lene M. Favrholdt
,
Ruben Hoeksma
,
Kim S. Larsen
,
Adam Polak
,
Bertrand Simon
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2210.02775
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2210.02775
Paging is a prototypical problem in the area of online algorithms. It has\nalso played a central role in the development of learning-augmented algorithms\n-- a recent line of research that aims to ameliorate the shortcomings of\nclassical worst-case analysis by giving algorithms access to predictions. Such\npredictions can typically be generated using a machine learning approach, but\nthey are inherently imperfect. Previous work on learning-augmented paging has\ninvestigated predictions on (i) when the current page will be requested again\n(reoccurrence predictions), (ii) the current state of the cache in an optimal\nalgorithm (state predictions), (iii) all requests until the current page gets\nrequested again, and (iv) the relative order in which pages are requested.\n We study learning-augmented paging from the new perspective of requiring the\nleast possible amount of predicted information. More specifically, the\npredictions obtained alongside each page request are limited to one bit only.\nWe consider two natural such setups: (i) discard predictions, in which the\npredicted bit denotes whether or not it is ``safe'' to evict this page, and\n(ii) phase predictions, where the bit denotes whether the current page will be\nrequested in the next phase (for an appropriate partitioning of the input into\nphases). We develop algorithms for each of the two setups that satisfy all\nthree desirable properties of learning-augmented algorithms -- that is, they\nare consistent, robust and smooth -- despite being limited to a one-bit\nprediction per request. We also present lower bounds establishing that our\nalgorithms are essentially best possible.\n
Related Topics
Concepts
Metadata
- Type
- preprint
- Landing Page
- http://arxiv.org/abs/2210.02775
- https://arxiv.org/pdf/2210.02775
- OA Status
- green
- Cited By
- 1
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4304195002
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4304195002Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2210.02775Digital Object Identifier
- Title
-
Paging with Succinct PredictionsWork title
- Type
-
preprintOpenAlex work type
- Publication year
-
2022Year of publication
- Publication date
-
2022-10-06Full publication date if available
- Authors
-
Antonios P. Antoniadis, Joan Boyar, Marek Eliáš, Lene M. Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, Bertrand SimonList of authors in order
- Landing page
-
https://arxiv.org/abs/2210.02775Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2210.02775Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2210.02775Direct OA link when available
- Concepts
-
Paging, Computer science, Operating systemTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2023: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4304195002 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2210.02775 |
| ids.openalex | https://openalex.org/W4304195002 |
| fwci | 0.17949637 |
| type | preprint |
| title | Paging with Succinct Predictions |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10397 |
| topics[0].field.id | https://openalex.org/fields/27 |
| topics[0].field.display_name | Medicine |
| topics[0].score | 0.04960000142455101 |
| topics[0].domain.id | https://openalex.org/domains/4 |
| topics[0].domain.display_name | Health Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2737 |
| topics[0].subfield.display_name | Physiology |
| topics[0].display_name | Nutrition and Health in Aging |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C50954386 |
| concepts[0].level | 2 |
| concepts[0].score | 0.780227780342102 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q656083 |
| concepts[0].display_name | Paging |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.5734747648239136 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C111919701 |
| concepts[2].level | 1 |
| concepts[2].score | 0.22230616211891174 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q9135 |
| concepts[2].display_name | Operating system |
| keywords[0].id | https://openalex.org/keywords/paging |
| keywords[0].score | 0.780227780342102 |
| keywords[0].display_name | Paging |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.5734747648239136 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/operating-system |
| keywords[2].score | 0.22230616211891174 |
| keywords[2].display_name | Operating system |
| language | |
| locations[0].id | pmh:oai:arXiv.org:2210.02775 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2210.02775 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2210.02775 |
| indexed_in | arxiv |
| authorships[0].author.id | https://openalex.org/A5050100279 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-6604-5581 |
| authorships[0].author.display_name | Antonios P. Antoniadis |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Antonios Antoniadis |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5068354624 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-0725-8341 |
| authorships[1].author.display_name | Joan Boyar |
| authorships[1].affiliations[0].raw_affiliation_string | SDU, Faculty of Science, Department of Mathematics and Computer Science, DK |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Joan Boyar |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | SDU, Faculty of Science, Department of Mathematics and Computer Science, DK |
| authorships[2].author.id | https://openalex.org/A5035053302 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-4583-8897 |
| authorships[2].author.display_name | Marek Eliáš |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Marek Eliáš |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5023065140 |
| authorships[3].author.orcid | https://orcid.org/0000-0003-3054-2997 |
| authorships[3].author.display_name | Lene M. Favrholdt |
| authorships[3].affiliations[0].raw_affiliation_string | SDU, Faculty of Science, Department of Mathematics and Computer Science, DK |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Lene M. Favrholdt |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | SDU, Faculty of Science, Department of Mathematics and Computer Science, DK |
| authorships[4].author.id | https://openalex.org/A5010930168 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-6553-7242 |
| authorships[4].author.display_name | Ruben Hoeksma |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Ruben Hoeksma |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5000210653 |
| authorships[5].author.orcid | https://orcid.org/0000-0003-0560-3794 |
| authorships[5].author.display_name | Kim S. Larsen |
| authorships[5].affiliations[0].raw_affiliation_string | SDU, Faculty of Science, Department of Mathematics and Computer Science, DK |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Kim S. Larsen |
| authorships[5].is_corresponding | False |
| authorships[5].raw_affiliation_strings | SDU, Faculty of Science, Department of Mathematics and Computer Science, DK |
| authorships[6].author.id | https://openalex.org/A5064315511 |
| authorships[6].author.orcid | https://orcid.org/0000-0003-4925-774X |
| authorships[6].author.display_name | Adam Polak |
| authorships[6].author_position | middle |
| authorships[6].raw_author_name | Adam Polak |
| authorships[6].is_corresponding | False |
| authorships[7].author.id | https://openalex.org/A5017741899 |
| authorships[7].author.orcid | https://orcid.org/0000-0002-2565-1163 |
| authorships[7].author.display_name | Bertrand Simon |
| authorships[7].countries | FR |
| authorships[7].affiliations[0].institution_ids | https://openalex.org/I4210144793 |
| authorships[7].affiliations[0].raw_affiliation_string | Centre de Calcul de l'IN2P3 |
| authorships[7].institutions[0].id | https://openalex.org/I4210144793 |
| authorships[7].institutions[0].ror | https://ror.org/04dcc3438 |
| authorships[7].institutions[0].type | facility |
| authorships[7].institutions[0].lineage | https://openalex.org/I1294671590, https://openalex.org/I4210133362, https://openalex.org/I4210144793 |
| authorships[7].institutions[0].country_code | FR |
| authorships[7].institutions[0].display_name | Centre de Calcul de l’Institut National de Physique Nucléaire et de Physique des Particules |
| authorships[7].author_position | last |
| authorships[7].raw_author_name | Bertrand Simon |
| authorships[7].is_corresponding | False |
| authorships[7].raw_affiliation_strings | Centre de Calcul de l'IN2P3 |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2210.02775 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Paging with Succinct Predictions |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10397 |
| primary_topic.field.id | https://openalex.org/fields/27 |
| primary_topic.field.display_name | Medicine |
| primary_topic.score | 0.04960000142455101 |
| primary_topic.domain.id | https://openalex.org/domains/4 |
| primary_topic.domain.display_name | Health Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2737 |
| primary_topic.subfield.display_name | Physiology |
| primary_topic.display_name | Nutrition and Health in Aging |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W1867121152, https://openalex.org/W2148873835, https://openalex.org/W2350131590, https://openalex.org/W1904017904, https://openalex.org/W2030857781, https://openalex.org/W2373862622, https://openalex.org/W2372591684 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2023 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:arXiv.org:2210.02775 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2210.02775 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2210.02775 |
| primary_location.id | pmh:oai:arXiv.org:2210.02775 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2210.02775 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2210.02775 |
| publication_date | 2022-10-06 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 2, 14, 23, 49, 214 |
| abstract_inverted_index.-- | 201, 209 |
| abstract_inverted_index.It | 11 |
| abstract_inverted_index.We | 106, 184, 218 |
| abstract_inverted_index.an | 83, 177 |
| abstract_inverted_index.be | 46, 71 |
| abstract_inverted_index.by | 37 |
| abstract_inverted_index.in | 5, 17, 82, 101, 144, 172 |
| abstract_inverted_index.is | 1, 153 |
| abstract_inverted_index.it | 152 |
| abstract_inverted_index.of | 8, 20, 26, 79, 114, 119, 180, 189, 198 |
| abstract_inverted_index.on | 59, 64 |
| abstract_inverted_index.or | 150 |
| abstract_inverted_index.to | 30, 41, 132, 155, 213 |
| abstract_inverted_index.(i) | 65, 141 |
| abstract_inverted_index.all | 88 |
| abstract_inverted_index.and | 96, 207 |
| abstract_inverted_index.are | 54, 104, 130, 226 |
| abstract_inverted_index.bit | 134, 147, 164 |
| abstract_inverted_index.can | 44 |
| abstract_inverted_index.for | 187 |
| abstract_inverted_index.is, | 203 |
| abstract_inverted_index.new | 112 |
| abstract_inverted_index.not | 151 |
| abstract_inverted_index.one | 133 |
| abstract_inverted_index.per | 216 |
| abstract_inverted_index.the | 6, 18, 32, 67, 76, 80, 91, 98, 111, 163, 167, 173, 181, 190 |
| abstract_inverted_index.two | 137, 191 |
| abstract_inverted_index.(for | 176 |
| abstract_inverted_index.(ii) | 75 |
| abstract_inverted_index.(iv) | 97 |
| abstract_inverted_index.More | 122 |
| abstract_inverted_index.aims | 29 |
| abstract_inverted_index.also | 219 |
| abstract_inverted_index.area | 7 |
| abstract_inverted_index.best | 228 |
| abstract_inverted_index.each | 127, 188 |
| abstract_inverted_index.from | 110 |
| abstract_inverted_index.line | 25 |
| abstract_inverted_index.next | 174 |
| abstract_inverted_index.page | 69, 93, 128, 169 |
| abstract_inverted_index.role | 16 |
| abstract_inverted_index.such | 139 |
| abstract_inverted_index.that | 28, 193, 202, 224 |
| abstract_inverted_index.this | 157 |
| abstract_inverted_index.when | 66 |
| abstract_inverted_index.will | 70, 170 |
| abstract_inverted_index.work | 58 |
| abstract_inverted_index.(iii) | 87 |
| abstract_inverted_index.being | 211 |
| abstract_inverted_index.cache | 81 |
| abstract_inverted_index.evict | 156 |
| abstract_inverted_index.input | 182 |
| abstract_inverted_index.lower | 221 |
| abstract_inverted_index.order | 100 |
| abstract_inverted_index.page, | 158 |
| abstract_inverted_index.pages | 103 |
| abstract_inverted_index.phase | 160, 175 |
| abstract_inverted_index.state | 78 |
| abstract_inverted_index.study | 107 |
| abstract_inverted_index.until | 90 |
| abstract_inverted_index.using | 48 |
| abstract_inverted_index.where | 162 |
| abstract_inverted_index.which | 102, 145 |
| abstract_inverted_index.(state | 85 |
| abstract_inverted_index.Paging | 0 |
| abstract_inverted_index.access | 40 |
| abstract_inverted_index.again, | 95 |
| abstract_inverted_index.amount | 118 |
| abstract_inverted_index.bounds | 222 |
| abstract_inverted_index.giving | 38 |
| abstract_inverted_index.online | 9 |
| abstract_inverted_index.paging | 61, 109 |
| abstract_inverted_index.played | 13 |
| abstract_inverted_index.recent | 24 |
| abstract_inverted_index.robust | 206 |
| abstract_inverted_index.setups | 192 |
| abstract_inverted_index.smooth | 208 |
| abstract_inverted_index.central | 15 |
| abstract_inverted_index.current | 68, 77, 92, 168 |
| abstract_inverted_index.denotes | 148, 165 |
| abstract_inverted_index.despite | 210 |
| abstract_inverted_index.develop | 185 |
| abstract_inverted_index.discard | 142 |
| abstract_inverted_index.limited | 131, 212 |
| abstract_inverted_index.machine | 50 |
| abstract_inverted_index.natural | 138 |
| abstract_inverted_index.present | 220 |
| abstract_inverted_index.problem | 4 |
| abstract_inverted_index.request | 129 |
| abstract_inverted_index.satisfy | 194 |
| abstract_inverted_index.setups: | 140 |
| abstract_inverted_index.whether | 149, 166 |
| abstract_inverted_index.Previous | 57 |
| abstract_inverted_index.``safe'' | 154 |
| abstract_inverted_index.analysis | 36 |
| abstract_inverted_index.consider | 136 |
| abstract_inverted_index.learning | 51 |
| abstract_inverted_index.obtained | 125 |
| abstract_inverted_index.possible | 117 |
| abstract_inverted_index.relative | 99 |
| abstract_inverted_index.request. | 217 |
| abstract_inverted_index.requests | 89 |
| abstract_inverted_index.research | 27 |
| abstract_inverted_index.alongside | 126 |
| abstract_inverted_index.and\n(ii) | 159 |
| abstract_inverted_index.approach, | 52 |
| abstract_inverted_index.but\nthey | 53 |
| abstract_inverted_index.desirable | 196 |
| abstract_inverted_index.generated | 47 |
| abstract_inverted_index.has\nalso | 12 |
| abstract_inverted_index.only.\nWe | 135 |
| abstract_inverted_index.predicted | 120 |
| abstract_inverted_index.requested | 72 |
| abstract_inverted_index.requiring | 115 |
| abstract_inverted_index.they\nare | 204 |
| abstract_inverted_index.typically | 45 |
| abstract_inverted_index.algorithms | 39, 186, 200 |
| abstract_inverted_index.all\nthree | 195 |
| abstract_inverted_index.ameliorate | 31 |
| abstract_inverted_index.imperfect. | 56 |
| abstract_inverted_index.inherently | 55 |
| abstract_inverted_index.properties | 197 |
| abstract_inverted_index.the\nleast | 116 |
| abstract_inverted_index.worst-case | 35 |
| abstract_inverted_index.algorithms. | 10 |
| abstract_inverted_index.appropriate | 178 |
| abstract_inverted_index.consistent, | 205 |
| abstract_inverted_index.development | 19 |
| abstract_inverted_index.essentially | 227 |
| abstract_inverted_index.perspective | 113 |
| abstract_inverted_index.possible.\n | 229 |
| abstract_inverted_index.predictions | 63 |
| abstract_inverted_index.establishing | 223 |
| abstract_inverted_index.information. | 121 |
| abstract_inverted_index.partitioning | 179 |
| abstract_inverted_index.predictions, | 143, 161 |
| abstract_inverted_index.predictions. | 42 |
| abstract_inverted_index.prototypical | 3 |
| abstract_inverted_index.requested.\n | 105 |
| abstract_inverted_index.shortcomings | 33 |
| abstract_inverted_index.be\nrequested | 171 |
| abstract_inverted_index.of\nclassical | 34 |
| abstract_inverted_index.predictions), | 74, 86 |
| abstract_inverted_index.specifically, | 123 |
| abstract_inverted_index.algorithms\n-- | 22 |
| abstract_inverted_index.into\nphases). | 183 |
| abstract_inverted_index.the\npredicted | 146 |
| abstract_inverted_index.gets\nrequested | 94 |
| abstract_inverted_index.our\nalgorithms | 225 |
| abstract_inverted_index.the\npredictions | 124 |
| abstract_inverted_index.Such\npredictions | 43 |
| abstract_inverted_index.has\ninvestigated | 62 |
| abstract_inverted_index.learning-augmented | 21, 60, 108, 199 |
| abstract_inverted_index.optimal\nalgorithm | 84 |
| abstract_inverted_index.one-bit\nprediction | 215 |
| abstract_inverted_index.again\n(reoccurrence | 73 |
| cited_by_percentile_year.max | 94 |
| cited_by_percentile_year.min | 89 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 8 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/2 |
| sustainable_development_goals[0].score | 0.4099999964237213 |
| sustainable_development_goals[0].display_name | Zero hunger |
| citation_normalized_percentile.value | 0.4802032 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |