Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning-Augmented Search Data Structures
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes learning-augmented skip lists and KD trees that use an erroneous frequency oracle to place frequently queried items higher, achieving near-optimal expected search time (entropy-bounded) and robustness to bad predictions.
Problem
Search data structures (skip lists, KD trees) are oblivious to query frequency distributions, so they are suboptimal for skewed (e.g., Zipfian) query workloads; existing learning-augmented BST work does not handle dynamic insertions, partial orders, or high-dimensional data.
Approach
Use an oracle's predicted per-item query frequencies to deterministically promote high-frequency items to higher skip-list levels (threshold p_i >= (2^l-1)/n) while keeping randomized promotion for others, and build KD trees by splitting on axes that balance predicted query probability, including high-frequency non-data queries.
Key results
- Learning-augmented skip list achieves expected search time at most 20+2*sum f_i min(log 1/p_i, log n) and matches the entropy lower bound up to nearly a factor of two with perfect oracle.
- On CAIDA data, the learning-augmented skip list roughly halves query time (about 1.86x speed-up at largest query size), with average speed-ups of 1.45x on AOL and 1.63x on CAIDA.
- On the Stanford Lucy point cloud, the learning-augmented KD tree yields average query depth 15.1 versus 17.6 for a traditional KD tree.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use predicted query frequencies to guide skip-list promotion | Skip lists · Synthetic Zipfian distributions | query speed-up: 1.33 up to 7.76 | Helped |
| Use historical query frequencies to guide skip-list construction | Skip lists · AOL | query speed-up: 1.45 | Helped |
| Use historical query frequencies to guide skip-list construction | Skip lists · CAIDA | query speed-up: 1.63 | Helped |
| Use accurate query frequencies to guide skip-list construction | Skip lists · CAIDA, largest query size | query speed-up: 1.86× | Helped |
| Use noisy historical frequencies rather than perfect query-frequency predictions | Learning-augmented skip list · CAIDA temporal-change robustness test | query time | Helped |
| Use noisy query-frequency predictions to construct the KD tree | KD trees · Synthetic Zipfian distributions with noise | average query depth | Mixed |
| Arrange Zipfian query weights smoothly over space instead of randomly (ablation) | Learning-augmented KD tree · Synthetic 3D Zipfian distributions | average query depth | Helped |
| Use query frequencies to guide KD-tree construction | KD trees · Stanford Lucy point cloud, binned samples | average query depth: 17.6 -> 15.1 | Helped |
Surprising findings
- The learning-augmented skip list's speed-up on CAIDA (1.86x) was close to theoretical speed-up (1.81x) on a Zipfian dataset with exponent 1.37, which the authors describe as perhaps coincidental.
- Their skip list is robust to arbitrarily poor predictions with expected search time O(log n), matching the oblivious skip list.
Limitations
- Theoretical guarantees for KD trees are in terms of entropy of query distribution over the whole discretized space, and the KD tree analysis for noisy oracles is only sketched in the appendix.
- Skip list analysis assumes queries are made to dataset items; extension to general search-space queries is only described as generalizing.
- Empirical evaluation on real data uses a single temporal split and time-based oracle; robustness to distribution shift was shown only on limited trace data.
Experimental setup
Datasets: AOL search query dataset CAIDA IP traffic dataset synthetic Zipfian distributions Stanford Lucy mesh point cloud
Benchmarks: CAIDA traffic data AOL search queries synthetic Zipfian data Stanford Lucy point cloud
Metrics: expected search time query time average query depth insertion time speed-up factor
Baselines: traditional skip list traditional KD tree oblivious balanced KD tree
Builds on: learning-augmented binary search trees (Lin et al., ICML 2022) skip lists KD trees Huffman coding
Closest papers by meaning
- On the Power of Learning-Augmented Search Trees (ICML 2025 · similarity 0.91)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.88)
- Robust Learning-Augmented Dictionaries (ICML 2024 · similarity 0.84)
- Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.84)
- Scenario-Based Robust Optimization of Tree Structures (AAAI 2025 · similarity 0.84)
- Binary Search with Distributional Predictions (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.