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

Feb, 2024

通过学习增强算法的角度探索排序问题，其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境：在第一种情境中，为每个项目提供了其在已排序列表中的位置预测；在第二种情境中，我们假设存在一种 “快速但不精确” 的方法来比较项目，除此之外还有慢而准确的比较。对于这两种情境，我们设计了新的简单算法，仅使用 O (Σi log ηi) 个精确比较，其中 ηi 是第 i 个元素的适当定义的预测误差。特别是，随着预测质量的下降，比较次数从 O (n) 平滑地降低到 O (nlogn)。我们证明在所考虑的误差度量方面，比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。

Nov, 2023

用机器学习技术改进估计频率的算法，特别是使用了重要元素预测的算法，在一些参数范围内以及加入重要元素预测后，理论上超越了之前算法的性能，并在实验中取得了优于其他方法的表现。

Dec, 2023

本文从理论上证明，在数据分布的温和假设下，具有与非学习方法相同空间复杂度的学习索引可以在期望的 O (loglog n) 查询时间内回答查询，从而进一步巩固了学习索引的实证成功。

Jun, 2023

该论文研究了基于机器学习建议的在线缓存模型，提出了一种新的算法来解决缓存问题，该算法适用于低误差情况下的预测，具有低的竞争比率；通过改进算法和提供下限，有望进一步提高算法性能。

Oct, 2019

本论文研究了将预测融入 online list labeling 问题中，提出了一种新的数据结构并给出了 worst-case 和 stochastic error 两种模型的保证，以预测误差作为保证的上界，同时在实验中展示了该数据结构在实际应用中的表现。

May, 2023

使用机器学习和加强式算法提高缓存置换的性能

Jun, 2021

该论文研究了在不确定性条件下，利用学习增强算法处理排序和超图方向问题，并提出了针对准确和错误预测的性能保证算法，可以通过查询提高不确定性元素的精确度，从而最小化问题求解所需的查询数量。

May, 2023

本文提出了一种基于机器学习的辅助估计算法来解决大型数据集中不同元素数量的估计问题，并证明了当预测器正确的逼近因子为常数时，可以显著降低样本复杂度。

Jun, 2021

本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法，该算法可以将图按照展开器分簇，并可以提高聚类的准确性，同时通过估计图中节点的随机游走的分布，实现对谱嵌入的点积访问，并使用谱嵌入进行超平面划分，从而实现聚类。

Jan, 2021