Robust Learning-Augmented Dictionaries

arXiv:2402.09687v1 Announce Type: cross
Abstract: We present the first learning-augmented data structure for implementing dictionaries with optimal consistency and robustness. Our data structure, named RobustSL, is a skip list augmented by predictions of access frequencies of elements in a data sequence. With proper predictions, RobustSL has optimal consistency (achieves static optimality). At the same time, it maintains a logarithmic running time for each operation, ensuring optimal robustness, even if predictions are generated adversarially. Therefore, RobustSL has all the advantages of …

abstract arxiv augmented data cs.ds cs.lg data list predictions robust robustness type