# Privacy-Preserving Learning-Augmented Data Structures

arXiv: https://arxiv.org/abs/2510.00165 · HTML: https://mlsanity.com/paper/2510.00165/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 40 references that are in the map.
- First posted on arXiv 30 Sep 2025.

## Builds on (most cited first, 17 of 17)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [On Tradeoffs in Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.12770/) (2025)
- [Fast Partitioned Learned Bloom Filter](https://mlsanity.com/paper/2306.02846/) (2023)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [On the Power of Learning-Augmented Search Trees](https://mlsanity.com/paper/2211.09251/) (2022)
- [HiFlash: A History Independent Flash Device](https://mlsanity.com/paper/1511.05180/) (2015)
- [Biased Predecessor Search](https://mlsanity.com/paper/1707.01182/) (2017)
- [Zip Trees](https://mlsanity.com/paper/1806.06726/) (2018)
- [Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent](https://mlsanity.com/paper/2307.07660/) (2023)

## Abstract (arXiv)

Learning-augmented data structures use predicted frequency estimates to retrieve frequently occurring database elements faster than standard data structures. Recent work has developed data structures that optimally exploit these frequency estimates while maintaining robustness to adversarial prediction errors. However, the privacy and security implications of this setting remain largely unexplored. In the event of a security breach, data structures should reveal minimal information beyond their current contents. This is even more crucial for learning-augmented data structures, whose layout adapts to the data. A data structure is history independent if its memory representation reveals no information about past operations except what is inferred from its current contents. In this work, we take the first step towards privacy and security guarantees in this setting by proposing the first learning-augmented data structure that is strongly history independent, robust, and supports dynamic updates. To achieve this, we introduce two techniques: thresholding, which automatically makes any learning-augmented data structure robust, and pairing, a simple technique that provides strong history independence in the dynamic setting. Our experimental results demonstrate a tradeoff between security and efficiency but are still competitive with the state of the art.