Time To Replace Your Filter: How Maplets Simplify System Design
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911195528691712 |
|---|---|
| author | Bender, Michael A. Conway, Alex Farach-Colton, Martín Johnson, Rob Pandey, Prashant |
| author_facet | Bender, Michael A. Conway, Alex Farach-Colton, Martín Johnson, Rob Pandey, Prashant |
| contents | Filters such as Bloom, quotient, and cuckoo filters are fundamental building blocks providing space-efficient approximate set membership testing. However, many applications need to associate small values with keys-functionality that filters do not provide. This mismatch forces complex workarounds that degrade performance. We argue that maplets-space-efficient data structures for approximate key-value mappings-are the right abstraction. A maplet provides the same space benefits as filters while natively supporting key-value associations with one-sided error guarantees. Through detailed case studies of SplinterDB (LSM-based key-value store), Squeakr (k-mer counter), and Mantis (genomic sequence search), we identify the common patterns and demonstrate how a unified maplet abstraction can lead to simpler designs and better performance. We conclude that applications benefit from defaulting to maplets rather than filters across domains including databases, computational biology, and networking. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05518 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Time To Replace Your Filter: How Maplets Simplify System Design Bender, Michael A. Conway, Alex Farach-Colton, Martín Johnson, Rob Pandey, Prashant Data Structures and Algorithms Filters such as Bloom, quotient, and cuckoo filters are fundamental building blocks providing space-efficient approximate set membership testing. However, many applications need to associate small values with keys-functionality that filters do not provide. This mismatch forces complex workarounds that degrade performance. We argue that maplets-space-efficient data structures for approximate key-value mappings-are the right abstraction. A maplet provides the same space benefits as filters while natively supporting key-value associations with one-sided error guarantees. Through detailed case studies of SplinterDB (LSM-based key-value store), Squeakr (k-mer counter), and Mantis (genomic sequence search), we identify the common patterns and demonstrate how a unified maplet abstraction can lead to simpler designs and better performance. We conclude that applications benefit from defaulting to maplets rather than filters across domains including databases, computational biology, and networking. |
| title | Time To Replace Your Filter: How Maplets Simplify System Design |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.05518 |