2024/10/02 by Skachkov, Daniel, Ponomaryov, Denis, Dorn, Yuri +1
#Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2410.01760
We address the problem of learning-augmented online caching in the scenario when each request is accompanied by a prediction of the next occurrence of the requested page. We improve currently known bounds on the competitive ratio of the BlindOracle algorithm, which evicts a page predicted to be requested last. We also prove a lower bound on the competitive ratio of any randomized algorithm and show that a combination of the BlindOracle with the Marker algorithm achieves a competitive ratio that is optimal up to some constant.