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.

我们提出了第一个学习增强的数据结构，用于实现拥有最佳一致性和鲁棒性的字典。我们的数据结构名为RobustSL，它是一个带有数据序列中元素访问频率预测的跳表。通过正确的预测，RobustSL可以实现最佳一致性（达到静态最优性）。同时，它保持每个操作的对数运行时间，确保了最佳的鲁棒性，即使预测是针对性生成的。因此，RobustSL具备了Lin、Luo和Woodruff（ICML 2022）以及Cao等人（arXiv 2023）最近提出的学习增强数据结构的所有优点，并提供了先前工作中缺失的鲁棒性保证。数值实验表明，RobustSL在使用合成和真实数据集时优于其他替代数据结构。

鲁棒学习增强字典