A treap is a classic randomized binary search tree data structure that is easy to implement and supports O(\log n) expected time access. However, classic treaps do not take advantage of the input distribution or patterns in the input. Given recent advances in algorithms with predictions, we propose pairing treaps with machine advice to form a learning-augmented treap. We are the first to propose a learning-augmented data structure that supports binary search tree operations such as range-query and successor functionalities. With the assumption that we have access to advice from a frequency estimation oracle, we assign learned priorities to the nodes to better improve the treap's structure. We theoretically analyze the learning-augmented treap's performance under various input distributions and show that under those circumstances, our learning-augmented treap has stronger guarantees than classic treaps and other classic tree-based data structures. Further, we experimentally evaluate our learned treap on synthetic datasets and demonstrate a performance advantage over other search tree data structures. We also present experiments on real world datasets with known frequency estimation oracles and show improvements as well.
翻译:treap 是一种典型的随机二进制搜索树数据结构, 易于执行和支持 O( log n n) 的预期时间访问。 但是, 经典的treap 并没有利用输入分布或输入模式。 鉴于最近算法与预测的进展, 我们提议将treap 与机器建议配对成一个学习增强的treap 。 我们首先提出一个学习增强的数据结构, 支持二进制搜索树操作, 如范围查询和后续功能 。 假设我们能从频率估计或触角获得建议, 我们给节点分配了学到的优先事项, 以便更好地改进treap的结构。 我们从理论上分析学习增强的treap 在各种输入分布下的表现, 显示在这种情况下, 我们的学习增强的treap 要比经典的treap 和其他经典的树基数据结构更有保障。 此外, 我们实验了我们在合成数据集上学到的treatreaptreap, 并展示了在搜索树组数据结构上已知的性能优势。