Robust Learning-Augmented Dictionaries
Ali Zeynali Shahin Kamali Mohammad Hajiesmaili
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 the recent learning-augmented data structures of Lin, Luo, and
Woodruff (ICML 2022) and Cao et al. (arXiv 2023), while providing robustness
guarantees that are absent in the previous work. Numerical experiments show
that RobustSL outperforms alternative data structures using both synthetic and
real datasets.