hesela.devProteus range filter
Proteus is an approximate range-emptiness filter that tunes a uniform-depth trie and a prefix Bloom filter using sampled queries.
Its CPFPR model chooses prefix lengths under a space budget; either component can receive the whole budget. The RocksDB integration selects each SST's design at construction, using a changing query sample. Updating that sample does not retune an already-built filter. [1]
The pinned API uses an inclusive left bound and exclusive right bound. Its string Bloom path can conservatively include the right boundary. The getMemoryUsage method omits the prefix Bloom filter, so it is not total filter memory. [2]
The artifact uses RocksDB 6.20.3 and warns that its custom range-FPR statistics apply only to forward iterators. It also contains modeling changes made after the paper. [3]
Relations
- related
- Succinct range filter, Rosetta range filter, Grafite range filter, Prefix Bloom filter, Sorted string table
Limitations
- The workload-shift experiments interleave writes and filter reconstruction; they do not establish automatic adaptation for unchanged SSTs in a read-only workload. [1]
Citations
- Knorr et al. Proteus: A Self-Designing Range Filter. SIGMOD 2022, pp. 1670-1684, sections 4 and 6. DOI: 10.1145/3514221.3526167.
- Proteus author code: Query endpoint contract and getMemoryUsage; commit 7580c5b8d184afd19f3fdaf10f782344bdf552f5.
- Proteus artifact README: post-paper modeling changes and forward-iterator FPR instrumentation; pinned commit 7580c5b8d184afd19f3fdaf10f782344bdf552f5.
Further reading
Sources & caveats
- Primary-source review of the SIGMOD paper and pinned author code; no Proteus execution or benchmark replication.