Learning Augmented Binary Search Trees

Honghao Lin, Tian Luo, David P. Woodruff

Abstract

Traditional binary search trees (BSTs) are designed to provide $O(\log n)$ access time by optimizing for the worst-case scenario. However, real-world data access patterns are often non-uniform, following skewed distributions where a small subset of items is queried frequently. This paper introduces the first learning-augmented BST, which replaces the random priorities of a standard Treap with frequency predictions from a machine learning model. By placing frequently accessed items closer to the root, this structure achieves near-optimal performance on skewed distributions while maintaining the robustness of traditional trees. Experimental results on synthetic and real-world datasets, including AOL search queries and CAIDA network traffic, demonstrate significant performance improvements over Splay trees and balanced BSTs.

Introduction

Binary Search Trees (BSTs) are fundamental components in computer science, serving as the backbone for database indexing, file systems, and kernel-level data management. Standard balanced BSTs, such as Red-Black or AVL trees, ensure that any operation takes $O(\log n)$ time. While this provides a reliable upper bound, it fails to exploit the non-uniformity inherent in practical workloads. In many applications, data access follows Zipfian distributions where a few "hot" items account for the majority of queries.

Existing solutions like Splay Trees attempt to adapt to these patterns dynamically, but they incur significant overhead due to frequent structural rotations. Alternatively, statically optimal trees require perfect prior knowledge of the distribution and often lack support for dynamic updates. This research proposes a middle ground: a learning-augmented Treap that leverages machine learning predictions to optimize search paths while remaining dynamic and robust against prediction errors.

Methodology: The Learning-Augmented Treap

The authors utilize the Treap as the foundational structure. A Treap is a hybrid data structure that maintains two properties simultaneously:

  1. Binary Search Tree Property: For any node, the left child's key is smaller and the right child's key is larger.
  2. Heap Property: Each node is assigned a priority, and a parent's priority must be greater than its children's.

In a classic Treap, priorities are assigned randomly to ensure the tree remains balanced with high probability. In the learning-augmented version, priorities are derived from a frequency estimation oracle. If a model predicts an item will be queried frequently, it is assigned a high priority, causing it to "float" toward the root of the tree and reducing its search depth.

Robustness and the "Shuffled" Modification

To ensure the data structure remains efficient even when data is adversarial or the ML model provides poor predictions, the authors introduced a "shuffled" modification. This involves mapping keys to random real numbers while maintaining the learned priorities, preventing the tree from becoming pathologically unbalanced. This ensures that even with a completely inaccurate model, the structure performs no worse than a standard randomized Treap.

Theoretical Guarantees

The paper provides several key theoretical proofs for the learning-augmented Treap:

  • Expected Depth: For the $i$-th most frequent item in the distribution, the expected depth in the tree is $O(\log i)$.
  • Static Optimality: The structure is proven to be statically optimal for Zipfian distributions, which are ubiquitous in real-world data.
  • Constant Time Access: For highly skewed distributions (where the Zipfian parameter $\alpha > 1$), the expected access time becomes $O(1)$, independent of the total number of elements $n$.

Experimental Evaluation

The researchers evaluated the performance of the learning-augmented Treap against standard BSTs (AVL, Red-Black) and Splay Trees using three primary data sources:

  1. Synthetic Zipfian Data: Controlled datasets with varying skewness parameters ($\alpha$).
  2. CAIDA Internet Traffic: IP flow data from a Chicago-to-Seattle backbone link.
  3. AOL Search Queries: A dataset of 21 million search queries following Zipf’s Law.

For real-world datasets, a Recurrent Neural Network (RNN) served as the frequency estimation oracle to provide the priorities.

Key Results

  • Efficiency Gains: On Zipfian distributions, the learned Treap outperformed Splay Trees by 25% and traditional balanced trees (AVL/Red-Black) by over 30% in terms of the number of comparisons.
  • Scalability: Experimental data confirmed the theoretical prediction of constant-time access for highly skewed distributions, showing that search time remained flat even as the dataset size increased.
  • Real-World Robustness: On the AOL and CAIDA datasets, the "shuffled" learned Treap significantly outperformed standard Treaps and remained competitive with highly optimized Red-Black trees, even when the ML model predictions were imperfect.

Discussion and Future Work

While the learning-augmented Treap shows great promise, the authors identify the "Oracle Overhead" as a practical limitation. In a real-world system, the time required to generate a prediction from a complex model like an RNN might exceed the time saved during tree traversal. Future research may focus on using lighter-weight models or hardware-accelerated oracles.

Additionally, while the structure supports range queries, the current "shuffled" modification is not yet optimized for range-based access patterns. The authors suggest that the principles of learning-augmentation could be extended to other complex structures, such as van Emde Boas trees or Biased Skip Lists, to further push the boundaries of data structure efficiency.

Summary updated

BibTeX
@inproceedings{lin2022learning,
  author = {Honghao Lin and Tian Luo and David P. Woodruff},
  title = {{Learning Augmented Binary Search Trees}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=cp4r5QHckV},
}

Loading related content...

Figure