# Learned Static Function Data Structures

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 78 references that are in the map.
- First posted on arXiv 31 Oct 2025.

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

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [NetFlow Datasets for Machine Learning-based Network Intrusion Detection Systems](https://mlsanity.com/paper/2011.09144/) (2020)
- [DeepZip: Lossless Data Compression using Recurrent Neural Networks](https://mlsanity.com/paper/1811.08162/) (2018)
- [The PGM-index: a multicriteria, compressed and learned approach to data indexing](https://mlsanity.com/paper/1910.06169/) (2019)
- [Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier](https://mlsanity.com/paper/1910.09131/) (2019)
- [Meta-Learning Neural Bloom Filters](https://mlsanity.com/paper/1906.04304/) (2019)
- [DeepBF: Malicious URL detection using Learned Bloom Filter and Evolutionary Deep Learning](https://mlsanity.com/paper/2103.12544/) (2021)
- [Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters](https://mlsanity.com/paper/1912.08258/) (2019)
- [Binary Fuse Filters: Fast and Smaller Than Xor Filters](https://mlsanity.com/paper/2201.01174/) (2022)
- [Daisy Bloom Filters](https://mlsanity.com/paper/2205.14894/) (2022)
- [Learned Monotone Minimal Perfect Hashing](https://mlsanity.com/paper/2304.11012/) (2023)
- [LeCo: Lightweight Compression via Learning Serial Correlations](https://mlsanity.com/paper/2306.15374/) (2023)
- [Squish: Near-Optimal Compression for Archival of Relational Datasets](https://mlsanity.com/paper/1602.04256/) (2016)
- [Fast Succinct Retrieval and Approximate Membership using Ribbon](https://mlsanity.com/paper/2109.01892/) (2021)
- [Tight Bounds for Monotone Minimal Perfect Hashing](https://mlsanity.com/paper/2207.10556/) (2022)
- [DeepMapping: Learned Data Mapping for Lossless Compression and Efficient Lookup](https://mlsanity.com/paper/2307.05861/) (2023)
- [Modern Minimal Perfect Hashing: A Survey](https://mlsanity.com/paper/2506.06536/) (2025)
- [Fast Prefix Search in Little Space, with Applications](https://mlsanity.com/paper/1804.04720/) (2018)
- [Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once](https://mlsanity.com/paper/2109.04548/) (2021)
- [PaCHash: Packed and Compressed Hash Tables](https://mlsanity.com/paper/2205.04745/) (2022)
- [SicHash -- Small Irregular Cuckoo Tables for Perfect Hashing](https://mlsanity.com/paper/2210.01560/) (2022)
- [CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions](https://mlsanity.com/paper/2305.16545/) (2023)
- [ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force](https://mlsanity.com/paper/2308.09561/) (2023)
- [Learned Compression of Nonlinear Time Series With Random Access](https://mlsanity.com/paper/2412.16266/) (2024)
- [MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing](https://mlsanity.com/paper/2503.10161/) (2025)
- [ε-Cost Sharding: Scaling Hypergraph-Based Static Functions and Filters to Trillions of Keys](https://mlsanity.com/paper/2503.18397/) (2025)

## Abstract (arXiv)

We consider the task of constructing a data structure for associating a static set of keys with values, while allowing arbitrary output values for queries involving keys outside the set. Compared to hash tables, these so-called static function data structures do not need to store the key set and thus use significantly less memory. Several techniques are known, with compressed static functions approaching the zero-order empirical entropy of the value sequence. In this paper, we introduce learned static functions, which use machine learning to capture correlations between keys and values. For each key, a model predicts a probability distribution over the values, from which we derive a key-specific prefix code to compactly encode the true value. The resulting codeword is stored in a classic static function data structure. This design allows learned static functions to break the zero-order entropy barrier while still supporting point queries. Our experiments show substantial space savings: up to one order of magnitude on real data, and up to three orders of magnitude on synthetic data.