Algorithms for Caching and MTS with reduced number of predictions
Authors: Karim Ahmed Abdel Sadek, Marek Elias
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform an empirical evaluation of our caching algorithm F&R on the same datasets and with the same predictors as the previous works (Lykouris and Vassilvitskii, 2021; Antoniadis et al., 2023; Im et al., 2022). |
| Researcher Affiliation | Academia | Karim Abdel Sadek University of Amsterdam karim.abdel.sadek@student.uva.nl Marek Eliáš Department of Computing Sciences Bocconi University marek.elias@unibocconi.it |
| Pseudocode | Yes | Algorithm 1: Follower; Algorithm 2: Robustf (one phase) |
| Open Source Code | Yes | The code of our implementation can be found at https://github.com/marek-elias/caching/ |
| Open Datasets | Yes | Bright Kite dataset (Cho et al., 2011) contains data from a certain social network. ... Citi Bike dataset contains data about bike trips in a bike sharing platform Citi Bike. |
| Dataset Splits | No | The paper describes dataset usage and selection criteria, such as "choose instances corresponding to the first 100 users with the longest check-in sequences" and "trimming length of each instance to 25 000", but does not specify explicit training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide specific details about the hardware (e.g., CPU, GPU models, memory) used for running the experiments. |
| Software Dependencies | No | The paper mentions implementing algorithms and using predictors, but does not provide specific version numbers for any software dependencies or libraries. |
| Experiment Setup | Yes | Notes on implementation of F&R. We follow the recommendations in Section 3 except that Follower switches to Robust whenever its cost is α = 1 times higher compared to Belady in the same period. With higher α, the performance of F&R approaches Ft P on the considered datasets. With k = 10 (Bright Kite dataset), we use F = [1, 6, 9] corresponding to f(i) = i. Note that, with such small k, polynomial and exponential f would also give a very similar F. With k = 100 (Citi Bike dataset), we use exponential f(i) = 2i+1 1. With a-separated queries, Follower uses LRU heuristic when prediction is unavailable, and Robust ignores F, querying the predictor at each page fault separated from the previous query by at least a time steps. |