# Proteus: A Self-Designing Range Filter

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 53 references that are in the map.
- First posted on arXiv 30 Jun 2022.

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

- [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)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [SOSD: A Benchmark for Learned Indexes](https://mlsanity.com/paper/1911.13014/) (2019)
- [Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier](https://mlsanity.com/paper/1910.09131/) (2019)
- [Partitioned Learned Bloom Filter](https://mlsanity.com/paper/2006.03176/) (2020)
- [AsterixDB: A Scalable, Open Source BDMS](https://mlsanity.com/paper/1407.0454/) (2014)
- [Bloom Filters, Adaptivity, and the Dictionary Problem](https://mlsanity.com/paper/1711.01616/) (2017)
- [Adaptive Cuckoo Filters](https://mlsanity.com/paper/1704.06818/) (2017)
- [Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters](https://mlsanity.com/paper/1912.08258/) (2019)
- [Ribbon filter: practically smaller than Bloom and Xor](https://mlsanity.com/paper/2103.02515/) (2021)
- [GraphChi-DB: Simple Design for a Scalable Graph Database System -- on Just a PC](https://mlsanity.com/paper/1403.0701/) (2014)
- [Approximate Range Emptiness in Constant Time and Optimal Space](https://mlsanity.com/paper/1407.2907/) (2014)
- [Faster 64-bit universal hashing using carry-less multiplications](https://mlsanity.com/paper/1503.03465/) (2015)
- [vChain: Enabling Verifiable Boolean Range Queries over Blockchain Databases](https://mlsanity.com/paper/1812.02386/) (2018)
- [Coconut Palm: Static and Streaming Data Series Exploration Now in your Palm](https://mlsanity.com/paper/2006.13079/) (2020)

## Built on by (most cited first, 2 of 2)

- [Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads](https://mlsanity.com/paper/2308.07013/) (2023)
- [CAMAL: Optimizing LSM-trees via Active Learning](https://mlsanity.com/paper/2409.15130/) (2024)

## Abstract (arXiv)

We introduce Proteus, a novel self-designing approximate range filter, which configures itself based on sampled data in order to optimize its false positive rate (FPR) for a given space requirement. Proteus unifies the probabilistic and deterministic design spaces of state-of-the-art range filters to achieve robust performance across a larger variety of use cases. At the core of Proteus lies our Contextual Prefix FPR (CPFPR) model - a formal framework for the FPR of prefix-based filters across their design spaces. We empirically demonstrate the accuracy of our model and Proteus' ability to optimize over both synthetic workloads and real-world datasets. We further evaluate Proteus in RocksDB and show that it is able to improve end-to-end performance by as much as 5.3x over more brittle state-of-the-art methods such as SuRF and Rosetta. Our experiments also indicate that the cost of modeling is not significant compared to the end-to-end performance gains and that Proteus is robust to workload shifts.